A note on acyclic number of planar graphs
DOI:
https://doi.org/10.26493/1855-3974.1118.143Keywords:
Induced forest, acyclic number, planar graph, girthAbstract
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.
Downloads
Published
2017-03-09
Issue
Section
Articles
License
Articles in this journal are published under Creative Commons Attribution 4.0 International License
https://creativecommons.org/licenses/by/4.0/