×

zbMATH — the first resource for mathematics

Three-coloring planar graphs without short cycles. (English) Zbl 1185.05057
Summary: We prove that every planar graph without cycles of length 4, 6, 7 and 9 is 3-colorable.

MSC:
05C15 Coloring of graphs and hypergraphs
05C10 Planar graphs; geometric and topological aspects of graph theory
68R10 Graph theory (including graph drawing) in computer science
PDF BibTeX XML Cite
Full Text: DOI
References:
[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, 2, 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] 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)
[5] Jensen, T.R.; Toft, B., Graph coloring problems, (1995), Wiley New York · Zbl 0855.05054
[6] Sanders, D.P.; Zhao, Y., A note on the three coloring problem, Graphs combin., 11, 92-94, (1995)
[7] Steinberg, R.; Gimbel, J.; Kenndy, J.W.; Quintas, L.V., The state of the three color problem, Quo vadis, graph theory, Ann. discrete math., 55, 211-248, (1993)
[8] Zhang, L.; Wu, B., A note on 3-choosability of planar graphs without certain cycles, Discrete math., 297, 206-209, (2005) · Zbl 1070.05046
[9] B. Xu, On 3-colorable plane graphs without 5- and 7-cycles, J. Combin. Theory Ser. B, submitted for publication · Zbl 1108.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.