A note on acyclic number of planar graphs

Authors

  • Mirko Petruševski University St. Cyril and Methodius, Macedonia
  • Riste Škrekovski University of Ljubljana, Slovenia and Faculty of Information Studies, Slovenia and University of Primorska, Slovenia

DOI:

https://doi.org/10.26493/1855-3974.1118.143

Keywords:

Induced forest, acyclic number, planar graph, girth

Abstract

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.

Published

2017-03-09

Issue

Section

Articles