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