×

zbMATH — the first resource for mathematics

A note on 3-choosability of planar graphs without certain cycles. (English) Zbl 1070.05046
Summary: R. Steinberg [Ann. Discrete Math. 55, 211–248 (1993; Zbl 0791.05044)] asked whether every planar graph without 4 and 5 cycles is 3-colorable. O. V. Borodin [J. Graph Theory 21, 183–186 (1996; Zbl 0838.05039)], and independently D. P. Sanders and Y. Zhao [Graphs Comb. 11, 91–94 (1995; Zbl 0824.05023)], showed that every planar graph without any cycle of length between 4 and 9 is 3-colorable. We improve this result by showing that every planar graph without any cycle of length 4, 5, 6, or 9 is 3-choosable.

MSC:
05C15 Coloring of graphs and hypergraphs
05C38 Paths and cycles
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Abbott, H.L.; Zhou, B., On small faces in 4-critical planar graphs, Ars combin., 32, 203-207, (1991) · Zbl 0755.05062
[2] Alon, N.; Tarsi, M., Coloring and orientations of graphs, Combinatorica, 12, 2, 125-134, (1992) · Zbl 0756.05049
[3] Borodin, O.V., Structural properties of plane graphs without adjacent triangles and an application to 3-colorings, J. graph theory, 12, 2, 183-186, (1996) · Zbl 0838.05039
[4] Borodin, O.V., To the paper of H.L. abbott and B. zhou on 4-critical planar graphs, Ars combin., 43, 191-192, (1996) · Zbl 0881.05037
[5] O.V. Borodin, A.N. Glebov, A. Raspaud, M.R. Salavatipour, Planar graphs without cycles of length from 4 to 7 are 3-colorable, Working paper, undated, submitted for publication. · Zbl 1056.05052
[6] Grötzsch, H., Ein dreifarbensatz fur dreikreisfreie netze auf der kugel, Wiss. Z. martin-luther-univ. halle-Wittenberg, mat-natur. reche., 8, 109-120, (1959)
[7] Sanders, D.P.; Zhao, Y., A note on the three color problem, Graphs combin., 11, 91-94, (1995) · Zbl 0824.05023
[8] Steinberg, R., The state of the three color problem, (), 211-248 · Zbl 0791.05044
[9] Thomassen, C., 3-List-coloring planar graphs of girth 5, J. combin. theory ser. B, 64, 101-107, (1995) · Zbl 0822.05029
[10] L. Zhang, B. Wu, Three-choosable planar graphs without certain small cycles, Graph Theory Notes of New York 46 (2004) 27-30.
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.