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 question has already been answered by monkeymaths, but here is some more information.

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$.

Regarding the question of the largest induced forest of a planar graph (raised by monkeymaths), we can use the following theorem of Borodin.

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.


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.