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.
@article{1118,
title = {A note on acyclic number of planar graphs},
journal = {ARS MATHEMATICA CONTEMPORANEA},
volume = {14},
year = {2017},
doi = {10.26493/1855-3974.1118.143},
language = {EN},
url = {http://dml.mathdoc.fr/item/1118}
}
Petruševski, Mirko; Škrekovski, Riste. A note on acyclic number of planar graphs. ARS MATHEMATICA CONTEMPORANEA, Tome 14 (2017) . doi : 10.26493/1855-3974.1118.143. http://gdmltest.u-ga.fr/item/1118/