×

zbMATH — the first resource for mathematics

Acyclic colorings of planar graphs. (English) Zbl 0742.05041
In 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.

MSC:
05C15 Coloring of graphs and hypergraphs
05C10 Planar graphs; geometric and topological aspects of graph theory
05C05 Trees
PDF BibTeX XML Cite
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.