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 acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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