# Do planar graphs have an acyclic two-coloring?

A graph has an acyclic two-coloring if its vertices can be colored with two colors such that each color class spans a forest.

Does every planar graph have an acyclic two-coloring?

An affirmative answer would imply the four-color theorem, so I guess the answer has to be no, but I've failed to find a counterexample. Or would this problem be equivalent to the four-color theorem?

• The edges of any planar graph can be decomposed into $3$ forests, and this is tight ( en.m.wikipedia.org/wiki/Arboricity ), but you aren't decomposing all the edges, and your forests are induced subgraphs. Hmm... Nov 23 '16 at 13:06

G. Chartrand, H.V. Kronk, C.E. Wall showed in "The point-arboricity of a graph" (Israel J. Math., 6 (1968), pp. 169–175) that the vertex-set of any planar graph can be partitioned into three induced forests.

Later, Chartrand and Kronk provided an example showing that 'three' cannot be replaced by 'two', see "THE POINT-ARBORICITY OF PLANAR GRAPHS" (J. London Math. Soc., 44 (1969), pp. 612–616). It is the dual of the Tutte Graph.

I think it is still an open problem whether every planar graph with $n$ vertices has an induced forest on $n/2$ vertices.

The proof that every planar graph can be partitioned into three induced forests is actually quite easy. Let $$G$$ be a planar graph and $$v$$ be a vertex of degree at most $$5$$. By induction, $$G-v$$ can be partitioned into three induced forests. Since $$v$$ has degree at most $$5$$, one of these forests $$F$$ contains at most one neighbour of $$v$$. Thus, we can simply add $$v$$ to $$F$$.
Theorem (Borodin). Every planar graph has an acyclic $$5$$-colouring.
Here, an acyclic colouring is a proper colouring such that every $$2$$-coloured subgraph is acyclic (note that this is a different definition than in the original question, but is quite standard) . By taking the two largest colour classes of an acyclic $$5$$-colouring, we get that every $$n$$-vertex planar graph has an induced forest with at least $$\frac{2n}{5}$$ vertices. As far as I know, this is still the best lower bound. There are however improved bounds for triangle-free planar graphs. For example, Dross, Montassier, and Pinlou recently proved that every $$n$$-vertex triangle-free planar graph contains an induced forest with at least $$\frac{6n+7}{11}$$ vertices.