The List Coloring Conjecture for claw-free graphs
Let be a graph. Write for its chromatic number and for its list chromatic number, the least integer such that every assignment of lists of size to the vertices of admits a proper coloring from those lists. A graph is claw-free if it has no induced subgraph isomorphic to the claw . List Coloring Conjecture for claw-free graphs. Every claw-free satisfies
The conjecture asks when claw-free graphs are chromatic choosable. It is known for several subclasses, including elementary graphs and claw-free perfect graphs with clique number at most , but its general status is not resolved in the supplied source.
Equivalent formulations
Let be a claw-free graph, and let denote its list chromatic number and its maximum codegree. The claw-free list-coloring conjecture.
This would extend the paper's chromatic bound to list coloring and generalize the Weak List Coloring Conjecture. It is identified as a special case of a conjecture of Gravier and Maffray that list chromatic number equals chromatic number for every claw-free graph.
source: Linda Cook, Ross J. Kang, Eileen Robinson and Gabriëlle Zwaneveld, “Vu's conjecture holds for claw-free graphs”, arXiv:2510.15553 (2025).
References
5 papers in this index state this conjecture (2013–2023). The statement above is taken from the most recent of them; the others are arXiv:2207.11868, arXiv:2108.11816, arXiv:1712.05006, arXiv:1305.2566.
Source: Nandana K Vasudevan, K Somasundaram and J Geetha, “Every Elementary Graph is Chromatic Choosable”, arXiv:2312.00430 (2023).
Progress summary
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.