← All problems

Gravier–Maffray conjecture that claw-free graphs are chromatic-choosable

∀\forall finite claw-free graphs GG, ch⁡(G)=χ(G)\operatorname{ch}(G)=\chi(G), where a claw-free graph has no induced subgraph isomorphic to K1,3K_{1,3}, ch⁡(G)\operatorname{ch}(G) is its list-chromatic number, and χ(G)\chi(G) is its chromatic number.

References

Source: arXiv

Progress summary

Refreshed
Open · progress reported

A new result settles the conjecture for an important subclass, but the case of all claw-free graphs remains open.

Gravier and Maffray posed the conjecture in 1997: every claw-free graph should satisfy χl(G)=χ(G)\chi_l(G)=\chi(G). The full conjecture remains unresolved.

Known results

  • Gravier and Maffray (1997): elementary graphs with ω(G)≤3\omega(G)\leq 3 are chromatic-choosable.
  • Gravier and Maffray (1998): peculiar graphs are chromatic-choosable.
  • Gravier and Maffray (2004): claw-free perfect graphs with ω(G)≤3\omega(G)\leq 3 are chromatic-choosable.
  • Gravier, Maffray, and Pastor (2016): claw-free perfect graphs with ω(G)≤4\omega(G)\leq 4 are chromatic-choosable.

October 2026 elementary-graph theorem

Narayanan N, Nandana K. Vasudevan, and K. Somasundaram report that every elementary graph satisfies χl(G)=χ(G)\chi_l(G)=\chi(G), using their augmentation structure and Galvin’s theorem. This covers a substantial subclass, including line graphs of bipartite multigraphs and complements of bipartite graphs, but does not settle claw-free perfect graphs with clique cutsets or the full conjecture; the preprint result is unverified here.

Current status (as of October 2026): The conjecture is established for several subclasses, most recently all elementary graphs, but remains open for general claw-free graphs.

Sources

Solutions 0

No solutions have been posted yet.