zbMATH — the first resource for mathematics

On 3-colorable planar graphs without cycles of four lengths. (English) Zbl 1185.05061
Grötzsch’s Theorem states that planar graphs without 3-cycles are (vertex) 3-colorable. R. Steinberg conjectured that every planar graph without 4- or 5-cycles is 3-colorable, and P. Erdős asked if there is an integer \(k\geq5\) such that a planar graph without \(i\)-cycles for \(i= 4,5,\dots,k\) is 3-colorable [see R. Steinberg, “The state of the three color problem”, in Quo vadis, graph theory? A source book for challenges and directions. Ann. Discrete Math. 55, 211–248 (1993; Zbl 0791.05044)]. The best-known result answering Erdős’s question is that \(k\leq7\), proven by O. V. Borodin et al. [O.V. Borodin, A.N. Glebov, A. Raspaud, and M.R. Salavatipour, “Planar graphs without cycles of length from 4 to 7 are 3-colorable”, J. Comb. Theory, Ser. B 93, No. 2, 303–311 (2005; Zbl 1056.05052)]. Thus an interesting question is that of determining small sets of small integers whose absence as cycle lengths ensures 3-colorability. For sets of four omitted cycle-lengths, it is known that lacking \(\{4,5,6,9\}\)-cycles [L. Zhang and B. Wu, “A note on 3-choosability of planar graphs without certain cycles”, Discrete Math. 297, No. 1-3, 206–209 (2005; Zbl 1070.05046)], or \(\{4,5,7,9\}\)-cycles [W. F. Wang and Y. Wang, J. Liaoning Univ. Nat. Sci. 32, No. 4, 302–305 (2005)] or \(\{4,6,7,9\}\)-cycles [M. Chen, A. Raspaud, and W. F. Wang, “Three-coloring planar graphs without short cycles”, Inf. Process. Lett. 101, No. 3, 134–138 (2007; Zbl 1185.05057)] or \(\{4,5,6,8\}\)-cycles [W. F. Wang and M. Chen, “On 3-colorable planar graphs without prescribed cycles”, Discrete Math. 307, No. 22, 2820–2825 (2007; Zbl 1128.05025)] ensures 3-colorability. In this paper the authors prove that a planar graph without \(\{4,6,7,8\}\)-cycles is 3-colorable. They do so by proving that every 3-coloring of the vertices of a face of length 5, 9, 10, 11 or 12 extends to a 3-coloring of the whole graph, and by using a self-contained discharging argument. Beginning with work of C. Thomassen [J. Comb. Theory, Ser. B 64, No. 1, 101–107 (1995; Zbl 0822.05029)], similar results are being obtained on 3-choosability, that is, when lists of size at least three are assigned to each vertex and a (vertex) coloring is sought in which each vertex receives a color from its list [see, e.g., L. Zhang and B. Wu, [loc. cit.]; Graph Theory Notes N. Y. 46, 27–30 (2004)].
Reviewed by Joan Hutchinson (M.R. 2008g:05077)

05C15 Coloring of graphs and hypergraphs
05C10 Planar graphs; geometric and topological aspects of graph theory
05C38 Paths and cycles
Full Text: DOI
[1] Abbott, H.L.; Zhou, B., On small faces in 4-critical graphs, Ars combin., 32, 203-207, (1991) · Zbl 0755.05062
[2] Borodin, O.V., Structural properties of plane graphs without adjacent triangles and an application to 3-colorings, J. graph theory, 21, 183-186, (1996) · Zbl 0838.05039
[3] Borodin, O.V.; Glebov, A.N.; Raspaud, A.; Salavatipour, M.R., Planar graphs without cycles of length from 4 to 7 are 3-colorable, J. combin. theory ser. B, 93, 303-311, (2005) · Zbl 1056.05052
[4] Chen, M.; Raspaud, A.; Wang, W., Three-coloring planar graphs without short cycles, Inform. process. lett., 101, 134-138, (2007) · Zbl 1185.05057
[5] Grötzsch, H., Ein drefarbensatz fur dreikreisfreie netze auf der kugel, wiss. Z. martin-luther-univ. halle-Wittenberg, Mat-natur. reche., 8, 109-120, (1959)
[6] Jensen, T.R.; Toft, B., Graph coloring problems, (1995), Wiley New York · Zbl 0971.05046
[7] Steinberg, R., The state of the three color problem, (), 211-248 · Zbl 0791.05044
[8] Sanders, D.P.; Zhao, Y., A note on the three coloring problem, Graphs combin., 11, 92-94, (1995)
[9] Xu, B., On 3-colorable plane graphs without 5- and 7-cycles, J. combin. theory ser. B, 96, 958-963, (2006) · Zbl 1108.05046
[10] Wang, W.; Wang, Y., A note on the 3-choosable planar graphs, J. liaoning univ. nat. sci., 32, 302-305, (2005)
[11] W. Wang, M. Chen, On 3-colorable planar graphs without prescribed cycles, Discrete Math., accepted for publication
[12] Zhang, L.; Wu, B., A note on 3-choosability of planar graphs without certain cycles, Discrete math., 297, 206-209, (2005) · Zbl 1070.05046
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.