## 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.

References:
[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 Bojan.Mohar@uni-lj.si

##### Revised: avgust 20, 2002.