**Originator(s):**Michael O. Albertson (Smith College),
David M. Berman (U. New Orleans), Jin Akiyama (Tokai U.),
Mamoru Watanabe (Okayama U. Sci.),
Glenn G. Chappell (Alaska-Fairbanks)

**Definitions:**
A *linear forest* is a forest in which every component is a path.

**Conjectures:**
(1) Albertson-Berman [AB]:
Every planar graph has an induced subgraph with at least half of the vertices
that is a forest.

(2) Akiyama-Watanabe [AW]:
Every bipartite planar graph has an induced subgraph with at least 5/8 of the
vertices that is a forest.

(3) Chappell:
Every planar graph has an induced subgraph with more than 4/9 of the vertices
that is a linear forest.

**Background/motivation:**
Conjecture 1 would directly imply that every planar graph has an independent
set with at least one-quarter of the vertices, without using the Four Color
Theorem. Similarly, Conjecture 3 would directly strengthen the result of
Albertson [A], proved independently of the Four Color Theorem, which states
that every planar graph has an independent set with at least 2/9 of the
vertices. These questions generalize the independence number in the same
way that generalized coloring problems generalize the chromatic number.

**Comments/Partial results:**
Akiyama and Watanabe [AW] gave examples showing that Conjectures 1 and 2 are
best possible. Borodin [B] proved that every planar graph has an induced
forest with at least 2/5 of the vertices (the best known ratio), by proving
that every planar graph has a proper 5-coloring in which the union of any two
color classes induces a forest. For outerplanar graphs, Hosono [H] showed that
there is always an induced forest with at least 2/3 of the vertices, and this
is best possible (using disjoint triangles or the square of a path).
Maria Axenovich reports that Borodin and Glebov [BG] proved a stronger result
that implies the conjecture for planar graphs with girth at least 5:
the vertices can be partitioned into an independent set and another set that
induces a forest (the proof uses discharging).

For linear forests, the ratio is always at least 1/3, since Poh [Po] proved that the vertex set of a planar graph can be partitioned into three sets that induce linear forests (conjectured independently in [BM] and [M]). Chappell found examples showing that Conjecture 3 is best possible.

For linear forests in outerplanar graphs, each of [AEGW,BM,M] showed that the
vertex set of an outerplanar graph can be partitioned into two sets that
induce linear forests, and hence the ratio at least 1/2 is guaranteed for the
order of the largest induced linear forest. Chappell conjectured that every
outerplanar graph has an induced linear forest with more than 4/7 of the
vertices. Pelsmajer [Pe] proved this conjecture by showing that every
*n*-vertex outerplanar graph has an induced linear forest with at least
*\ceiling{(4n+2)/7}* vertices. The paper also contains Chappell's
examples showing that the result is sharp. (The presentation of results on
these problems is modeled on the introduction of [Pe].)

**References:**

[A] Albertson, M. O. A lower bound for the independence number of a planar
graph. J. Combinatorial Theory Ser. B 20 (1976), no. 1, 84--93.

[AB] Albertson, M. O.; Berman, D. M. A conjecture on planar graphs.
Graph Theory and Related Topics (J. A. Bondy and U. S. R. Murty, eds.),
(Academic Press, 1979), 357.

[AEGW] Akiyama, J.; Era, H.; Gervacio, S. V.; Watanabe, M.
Path chromatic numbers of graphs. J. Graph Theory 13 (1989), no. 5, 569--575.

[AW] Akiyama, J.; Watanabe, M. Maximum induced forests of planar graphs.
Graphs and Combinatorics 3 (1987), 201--202.

[B] Borodin, O. V. A proof of B. Grünbaum's conjecture on the acyclic
5-colorability of planar graphs. (Russian) Dokl. Akad. Nauk SSSR 231 (1976),
no. 1, 18--20.

[BG] Borodin, O. V.; Glebov, A. N. On the partition of a planar graph of girth
5 into an empty and an acyclic subgraph. (Russian) Diskretn. Anal. Issled.
Oper. Ser. 1 8 (2001), no. 4, 34--53.

[BM] Broere, I.; Mynhardt, C. M. Generalized colorings of outerplanar and
planar graphs. Graph theory with applications to algorithms and computer
science (Kalamazoo, Mich., 1984), 151--161, Wiley-Intersci. Publ., Wiley, New
York, 1985.

[H] Hosono, K. Induced forests in trees and outerplanar graphs.
Proc. Fac. Sci. Tokai Univ. 25 (1990), 27--29.

[M] Mihók, P. On vertex partition numbers of graphs.
Graphs and other combinatorial topics (Prague, 1982), 183--188,
Teubner-Texte Math., 59, Teubner, Leipzig, 1983.

[Pe] Pelsmajer, M.J. Maximum induced linear forests in outerplanar graphs.
Graphs and Combinatorics, 2003.

[Po] Poh, K. S. On the linear vertex-arboricity of a planar graph.
J. Graph Theory 14 (1990), no. 1, 73--75.