科研之友
微信
新浪微博
Facebook
分享链接
摘要
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.
- 出版日期2017
