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.