Gravier–Maffray conjecture that claw-free graphs are chromatic-choosable
finite claw-free graphs , , where a claw-free graph has no induced subgraph isomorphic to , is its list-chromatic number, and is its chromatic number.
References
- Elementary graphs are chromatic-choosable — arXiv — Narayanan N, Nandana K. Vasudevan, K. Somasundaram
Source: arXiv
Progress summary
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 . The full conjecture remains unresolved.
Known results
- Gravier and Maffray (1997): elementary graphs with are chromatic-choosable.
- Gravier and Maffray (1998): peculiar graphs are chromatic-choosable.
- Gravier and Maffray (2004): claw-free perfect graphs with are chromatic-choosable.
- Gravier, Maffray, and Pastor (2016): claw-free perfect graphs with are chromatic-choosable.
October 2026 elementary-graph theorem
Narayanan N, Nandana K. Vasudevan, and K. Somasundaram report that every elementary graph satisfies , 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.
Solutions 0
No solutions have been posted yet.