Ohba's chromatic-choosability conjecture

For a graph GG, let χ(G)\chi(G) be its chromatic number, and let χ(G)\chi_\ell(G) be its list chromatic number. A graph is chromatic-choosable when χ(G)=χ(G)\chi_\ell(G)=\chi(G). Ohba's conjecture. Any graph GG with at most 2χ(G)+12\chi(G)+1 vertices is chromatic-choosable. The supplied text says this conjecture was proved by Noel et al.; the bound is tight, since examples with 2χ(G)+22\chi(G)+2 vertices are not chromatic-choosable.

Sources & referencesView supporting material

Primary source

Nandana K Vasudevan, K Somasundaram and N Narayanan, “List-Coloring and Chromatic-Choosability – A Dynamic Survey”, arXiv:2606.31702 (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.