← All problems

Steinberg's conjecture on 3-coloring planar graphs without 4- or 5-cycles

16 years old · traced to

A planar graph is a graph that can be embedded in the plane. Steinberg's conjecture. Every planar graph with no cycles of length four or five is 33-colorable.

References

6 papers in this index state this conjecture (2010–2016). The statement above is taken from the most recent of them; the others are arXiv:1508.07890, arXiv:1409.4054, arXiv:1407.5138, arXiv:1208.3395, arXiv:1004.0582.

Status

  • Refuted: Vincent Cohen-Addad, Michael Hebdige, Daniel Kráľ, Zhentao Li, Esteban Salgado. Steinberg's Conjecture is false (arXiv, 2016) https://arxiv.org/abs/1604.05108

Source: Luke Postle and Robin Thomas, “Hyperbolic families and coloring graphs on surfaces”, arXiv:1609.06749 (2018).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.