# Dividing planar graph into two acycliс

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?

-
As you probably realize, this is a strengthening of the four colorability of planar graphs, so you should expect/hope to find a counterexample. –  user83827 Dec 10 '11 at 22:26
add comment

## 1 Answer

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.

-
Yes, there is a counterexample in [RW]. Thank you, Gerry! –  Alex Nelson Dec 11 '11 at 1:04
add comment