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?



Do planar graphs have an acyclic two-coloring?
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.


