Steinberg's Conjecture is false

2016/04/18 by Cohen-Addad, Vincent, Hebdige, Michael, Kral, Daniel +2 · 2 citations
#Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.1604.05108

Abstract

Steinberg conjectured in 1976 that every planar graph with no cycles of length four or five is 3-colorable. We disprove this conjecture.

Cited by

• Planar graphs without cycles of length 4 or 5 are (7m:2m)-DP-colorable
• Odd list-coloring of graphs of small Euler genus with no short cycles of specific types

Related

• The proof of Steinberg's three coloring conjecture
• Plane graphs without 4- and 5-cycles and without ext-triangular 7-cycles are 3-colorable
• A relaxation of Steinberg's Conjecture
• Three coloring via triangle counting
• (1,0,0)-colorability of planar graphs without cycles of length 4 or 6