← All problems

Dvořák–Kráľ–Nejedlý–Škrekovski girth-five planar square-coloring conjecture

11 years old · traced to

Let GG be a planar graph of girth at least 55, and let Δ\Delta be its maximum degree. Dvořák–Kráľ–Nejedlý–Škrekovski conjecture. There exists Δ0\Delta_0 such that, if Δ≥Δ0\Delta\ge\Delta_0, then

χ2(G)=Δ+2.\chi^2(G)=\Delta+2.

This conjecture concerns the sharp asymptotic bound in girth five and was confirmed by Bonamy, Cranston, and Postle.

References

2 papers in this index state this conjecture (2015–2022). The statement above is taken from the most recent of them; the others are arXiv:1508.03663.

Source: Daniel W. Cranston, “Coloring, List Coloring, and Painting Squares of Graphs (and other related problems)”, arXiv:2210.05915 (2026).

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.