zbMATH — the first resource for mathematics

Planar graphs without 4, 6, 8-cycles are 3-colorable. (English) Zbl 1144.05033
It was conjectured by Steinberg in 1976 that every planar graph without 4-cycles and 5-cycles is 3-colorable [see T. Jensen and B. Toft, Graph Coloring Problems, New York, NY: John Wiley & Sons (1995; Zbl 0855.05054)] and it was asked by Erdős whether there exists an integer \(k\) such that the absence of cycles with length from 4 to \(k\) in a planar graph guarantees its 3-colorability. In this paper the authors prove that every planar graph without cycles of length 4, 6, and 8 is 3-colorable.

05C15 Coloring of graphs and hypergraphs
Full Text: DOI
[1] Jensen R T, Toft B. Graph Coloring Problems. New York: Wiley, 1995 · Zbl 0855.05054
[2] 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)
[3] Steinberg R. The state of the three color problem. In: Gimbel J, Kenndy J W, Quintas L V, eds. Quo Vadis, Graph Theory? Annals of Discrete Math, Vol 55, 1993, 211–248 · Zbl 0791.05044
[4] Abbott H L, Zhou B. On small faces in 4-critical graphs. Ars Combin, 32: 203–207 (1991) · Zbl 0755.05062
[5] 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 · doi:10.1002/(SICI)1097-0118(199602)21:2<183::AID-JGT7>3.0.CO;2-N
[6] Sanders D P, Zhao Y. A note on the three coloring problem. Graphs Combin, 11: 92–94 (1995) · Zbl 0824.05023 · doi:10.1007/BF01787424
[7] 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 · doi:10.1016/j.jctb.2004.11.001
[8] Xu B. On 3-colorable plane graphs without 5-and 7-cycles. J Combin Theory Ser B, 96(6): 958–963 (2006) · Zbl 1108.05046 · doi:10.1016/j.jctb.2006.02.005
[9] Zhang L, Wu B. A note on 3-choosability of planar graphs without certain cycles. Discrete Math, 297: 206–209 (2005) · Zbl 1070.05046 · doi:10.1016/j.disc.2005.05.001
[10] Chen M, Raspaud A, Wang W. Three-coloring planar graphs without short cycles. Inform Process Lett, 101: 134–138 (2007) · Zbl 1185.05057 · doi:10.1016/j.ipl.2006.08.009
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.