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?

  • $\begingroup$ 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... $\endgroup$ – Pat Devlin 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.