Induced forests in planar graphs

The July 2002 Problem of the month is related to an old conjecture of Albertson and Berman [1]:

Conjecture: Let G be a simple planar graph of order n, and let k be the size of a largest set of vertices of G which induces a forest. Then k/n is at least 1/2.

Borodin's theorem about acyclic 5-colorability of planar graphs implies that k/n is at least 2/5.


[1] M. Albertson, D. Berman, A conjecture on planar graphs, in Graph Theory and Related Topics, ed. by Bondy and Murty, Academic Press, 1979, p. 357.

Send comments to

Revised: avgust 20, 2002.