← All problems

The List Coloring Conjecture for claw-free graphs

12 years old · documented by

Let GG be a graph. Write χ(G)\chi(G) for its chromatic number and χl(G)\chi_l(G) for its list chromatic number, the least integer kk such that every assignment of lists of size kk to the vertices of GG admits a proper coloring from those lists. A graph is claw-free if it has no induced subgraph isomorphic to the claw K1,3K_{1,3}. List Coloring Conjecture for claw-free graphs. Every claw-free GG satisfies

χl(G)=χ(G).\chi_l(G)=\chi(G).

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 33, but its general status is not resolved in the supplied source.

Equivalent formulations
  1. Let GG be a claw-free graph, and let χℓ(G)\chi_\ell(G) denote its list chromatic number and Δ2⁡(G)\operatorname{\Delta_2}(G) its maximum codegree. The claw-free list-coloring conjecture.

    χℓ(G)≤Δ2⁡(G)+3.\chi_\ell(G)\leq \operatorname{\Delta_2}(G)+3.

    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

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.