MathDB

The List Coloring Conjecture for claw-free graphs

From papers

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.

Progress summary

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

Equivalent formulations 1

Other statements of this same problem, merged from separate entries. Each is equivalent to the statement above — proving any one settles them all.

  1. List-coloring conjecture for claw-free graphs

    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).

Sources & referencesView supporting material

Primary source

Nandana K Vasudevan, K Somasundaram and J Geetha, “Every Elementary Graph is Chromatic Choosable”, arXiv:2312.00430 (2023).

Additional 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.

claw-free-graphsgraph-coloringlist-coloring

Solutions 0

No solutions have been posted yet.