×

zbMATH — the first resource for mathematics

Steinberg’s conjecture is false. (English) Zbl 1350.05018
Summary: Steinberg conjectured in 1976 that every planar graph with no cycles of length four or five is 3-colorable. We disprove this conjecture.

MSC:
05C10 Planar graphs; geometric and topological aspects of graph theory
05C15 Coloring of graphs and hypergraphs
PDF BibTeX XML Cite
Full Text: DOI arXiv
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, 183-186, (1996) · Zbl 0838.05039
[3] Borodin, O. V., Colorings of plane graphs: a survey, Discrete Math., 313, 517-539, (2013) · Zbl 1259.05042
[4] Borodin, O. V.; Glebov, A. N.; Jensen, T. R.; Raspaud, A., Planar graphs without triangles adjacent to cycles of length from 3 to 9 are 3-colorable, Sib. Èlektron. Mat. Izv., 3, 428-440, (2006) · Zbl 1119.05037
[5] Borodin, O. V.; Glebov, A. N.; Montassier, M.; Raspaud, A., Planar graphs without 5- and 7-cycles and without adjacent triangles are 3-colorable, J. Combin. Theory Ser. B, 99, 668-673, (2009) · Zbl 1184.05024
[6] Borodin, O. V.; Glebov, A. N.; Raspaud, A., Planar graphs without triangles adjacent to cycles of length from 4 to 7 are 3-colorable, Discrete Math., 310, 2584-2594, (2010) · Zbl 1203.05048
[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-331, (2005) · Zbl 1056.05052
[8] Borodin, O. V.; Raspaud, A., A sufficient condition for planar graphs to be 3-colorable, J. Combin. Theory Ser. B, 88, 17-27, (2003) · Zbl 1023.05046
[9] Jensen, T. R.; Toft, B., Graph coloring problems, (1995), John Wiley & Sons · Zbl 0855.05054
[10] Open problem garden
[11] Sanders, D. P.; Zhao, Y., A note on the three color problem, Graphs Combin., 11, 91-94, (1995) · Zbl 0824.05023
[12] Steinberg, R., The state of the three color problem, quo vadis, graph theory?, Ann. Discrete Math., 55, 211-248, (1993)
[13] Voigt, M., A non-3-choosable planar graph without cycles of length 4 and 5, Discrete Math., 307, 1013-1015, (2007) · Zbl 1112.05041
[14] Xu, B., On 3-colorable plane graphs without 5- and 7-cycles, J. Combin. Theory Ser. B, 96, 958-963, (2006) · 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.