Acyclic colorings of planar graphs (Q5905418): Difference between revisions

In 1969, \textit{G. Chartrand} and \textit{H. V. Kronk} [J. Lond. Math. Soc. 44, 612--616 (1969; Zbl 0175.50505)] showed that the vertex arboricity of a planar graph is at most 3. In other words, the vertex set of a planar graph can be partitioned into three sets each inducing a forest. In this paper it is proved that the vertex set of a planar graph can be partitioned into three sets such that each set induces a linear forest (i.e. a forest in which every component is a path). Also, for a given planar graph, one is guaranteed neither (a) a partition into two linear forests and a matching; nor (b) a partition into three linear forests such that every pair of colors induces an outerplanar graph. Part (b) shows that conjecture \(A\) proposed by \textit{L. Cowen}, \textit{R. H. Cowen} and \textit{D. R. Woodall} [J. Graph Theory 10, 187--195 (1986; Zbl 0596.05024)] is false.