Steinberg's Conjecture is false

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

paper · pdf · doi:10.48550/arxiv.1604.05108

Several typos fixed

arxiv created 2016/04/19 · arxiv updated 2016/04/20

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