A note on acyclic number of planar graphs
Mirko Petruševski, Riste Škrekovski · Ars Mathematica Contemporanea · 2017
The acyclic number a(G) of a graph G is the maximum order of an induced forest in G. The purpose of this short paper is to propose a conjecture that a(G) ≥ (1 − 3/(2g))n holds for every planar graph G of girth g and order n, which captures three known conjectures on the topic. In support of this conjecture, we prove a weaker result that a(G) ≥ (1 − 3/g)n holds. In addition, we give a construction showing that the constant 3/2 from the conjecture cannot be decreased.