Is it true that for any planar graph $(V,E)$ we can divide its set of vertices $V$ into two subsets $V=V_1\sqcup V_2$ such that subgraphs with these sets of vertices (and all edges between them) are both acyclic?
- Anybody can ask a question
- Anybody can answer
- The best answers are voted up and rise to the top
It says here, "Conjectures: (1) Albertson-Berman [AB]: Every planar graph has an induced subgraph with at least half of the vertices that is a forest." Also, "Akiyama and Watanabe [AW] gave examples showing that Conjectures 1 and 2 are best possible." So these papers (and the rest of the discussion and links) should be relevant. Here are the bibliographic details:
[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.
[AW] Akiyama, J.; Watanabe, M. Maximum induced forests of planar graphs. Graphs and Combinatorics 3 (1987), 201--202.