Acyclic colorings of planar graphs.

*(English)*Zbl 0742.05041In 1969, G. Chartrand and 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 L. Cowen, R. H. Cowen and D. R. Woodall [J. Graph Theory 10, 187–195 (1986; Zbl 0596.05024)] is false.

Reviewer: Ioan Tomescu (Bucureşti)

##### MSC:

05C15 | Coloring of graphs and hypergraphs |

05C10 | Planar graphs; geometric and topological aspects of graph theory |

05C05 | Trees |

Full Text:
DOI

##### References:

[1] | Broere, I.; Mynhardt, C., Generalized colorings of outerplanar and planar graphs, (), 151-161 · Zbl 0571.05017 |

[2] | Chartrand, G.; Kronk, H.V., The point-arboricity of planar graphs, J. London math. soc., 44, 612-616, (1969) · Zbl 0175.50505 |

[3] | Cowen, L.J.; Cowen, R.H.; Woodall, D.R., Defective colorings of graphs in surfaces: partition into subgraphs of bounded valence, J. graph theory, 10, 187-195, (1986) · Zbl 0596.05024 |

[4] | Stein, S.K., B-sets and coloring problems, Bull. amer. math. soc., 76, 805-806, (1970) · Zbl 0194.56004 |

[5] | Wegner, G., Note on a paper of B. grünbaum on acyclic colorings, Israel J. math., 14, 409-412, (1973) · Zbl 0265.05104 |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.