Havet–van den Heuvel–McDiarmid–Reed conjecture for nice graph classes

From papers

A graph class G\mathcal{G} is nice if it is minor-closed and does not contain K3,tK_{3,t} for some positive integer tt. Havet–van den Heuvel–McDiarmid–Reed conjecture. There exists Δ0\Delta_0 such that, whenever GGG\in\mathcal{G} and Δ(G)Δ0\Delta(G)\ge\Delta_0,

χ2(G)χ2(G)32Δ(G)+1.\chi^2(G)\le\chi_{\ell}^2(G)\le\left\lfloor\frac{3}{2}\Delta(G)\right\rfloor+1.

This asymptotic strengthening is posed for all nice classes; the survey gives asymptotic results for list coloring but does not report a resolution of this sharper bound.

Progress summary

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

Sources & referencesView supporting material

Primary source

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

Solutions 0

No solutions have been posted yet.