HEXAGONbeta

Claw-free perfect graphs are chromatic-choosable.

A mix of human-written and AI-generated textHuman understanding: all partsmath.CO — Combinatoricscs.DM — Discrete Mathematics

Contributed by Narayanan Narayanan ↗, Suchismita Mishra, Umesh Shankar

Version 1 / Nov 02, 2026 / CC BY 4.0

Abstract

We prove that every claw-free perfect graph GG satisfies ch⁡(G)=χ(G)=ω(G)\ch(G)=\chi(G)=\omega(G). More strongly, if SS is a clique of simplicial vertices of GG and k≥ω(G)k\ge\omega(G), every proper precoloring of SS extends to a proper coloring of GG from arbitrary lists of size kk on V(G)∖SV(G)\setminus S. The proof has three coloring steps: a mixed-list theorem for cobipartite graphs, a precoloring-extension theorem for elementary graphs built on Galvin's kernel method and a homogeneous-pair exchange argument, and a polynomial method (Combinatorial Nullstellensatz) argument for graphs of interval type in which a Vandermonde factor is transferred across each incomplete pair. The three coloring steps are assembled along the structure theorems of Chv\'atal--Sbihi, Maffray--Reed and Chudnovsky--Seymour, using double clique cutsets for composition. As a consequence, every perfect line graph is chromatic-choosable, recovering the theorem of Peterson and Woodall. Our precoloring extension theorem also resolves a conjecture posed by Chudnovsky and Seymour.

Provenance statement

Claude and GPT-6 were used to assist in formalizing some of the arguments. The proofs have been written by hand and verified by the authors. Then, it was polished with the help of GPT and Claude.

Tools used

OpenAI
ChatGPT
Anthropic
Claude Fable

References

  1. N. Alon, Combinatorial Nullstellensatz, Combinatorics, Probability and Computing 8 (1999), 7--29. doi:10.1017/S0963548398003411 (https://doi.org/10.1017/S0963548398003411).DOI
  2. N. Alon and M. Tarsi, Colorings and orientations of graphs, Combinatorica 12 (1992), 125--134. doi:10.1007/BF01204715 (https://doi.org/10.1007/BF01204715).DOI
  3. A. Bondy and U. S. R. Murty, Graph Theory , Graduate Texts in Mathematics, vol. 244, Springer, 2008.
  4. V. Chvátal and N. Sbihi, Recognizing claw-free perfect graphs, Journal of Combinatorial Theory, Series B 44 (1988), 154--176. doi:10.1016/0095-8956(88)90085-8 (https://doi.org/10.1016/0095-8956(88)90085-8).DOI
  5. M. Chudnovsky and P. Seymour, A structure theorem for claw-free perfect graphs, manuscript, June 15, 2003, revised March 8, 2004. https://web.math.princeton.edu/~pds/papers/claws/perfectclaws.pdf.link
  6. M. Chudnovsky and M. Plumettaz, The structure of claw-free perfect graphs, Journal of Graph Theory 75 (2014), 203--230. doi:10.1002/jgt.21732 (https://doi.org/10.1002/jgt.21732).DOI
  7. P. Erdős, A. L. Rubin and H. Taylor, Choosability in graphs , Congr.\ Numer.\ 26 (1980), 125--157.
  8. F. Galvin, The list chromatic index of a bipartite multigraph, Journal of Combinatorial Theory, Series B 63 (1995), 153--158. doi:10.1006/jctb.1995.1011 (https://doi.org/10.1006/jctb.1995.1011).DOI
  9. Sylvain Gravier and Fr é d é ric Maffray. Choice number of 3-colorable elementary graphs. Discrete Mathematics , 165--166:353--358, 1997.
  10. S. Gravier and F. Maffray, Graphs whose choice number is equal to their chromatic number, Journal of Graph Theory 27 (1998), 87--97. doi: 10.1002/(SICI)1097-0118(199802)27:2<87::AID-JGT4>3.0.CO;2-B (https://doi.org/10.1002/(SICI)1097-0118(199802)27:2<87::AID-JGT4>3.0.CO;2-B).DOI
Show all 17 referencesShow fewer references
  1. S. Gravier and F. Maffray, On the choice number of claw-free perfect graphs, Discrete Mathematics 276 (2004), 211--218. doi:10.1016/S0012-365X(03)00292-9 (https://doi.org/10.1016/S0012-365X(03)00292-9).DOI
  2. S. Gravier, F. Maffray and L. Pastor, On the choosability of claw-free perfect graphs, Graphs and Combinatorics 32 (2016), 2393--2413. doi:10.1007/s00373-016-1732-9 (https://doi.org/10.1007/s00373-016-1732-9).DOI
  3. F. Maffray and B. A. Reed, A description of claw-free perfect graphs, Journal of Combinatorial Theory, Series B 75 (1999), 134--156. doi:10.1006/jctb.1998.1872 (https://doi.org/10.1006/jctb.1998.1872).DOI
  4. Narayanan N, Nandana K. Vasudevan and K. Somasundaram, Elementary graphs are chromatic-choosable , arXiv:2610.16258, 2026. https://arxiv.org/abs/2610.16258.arXiv
  5. Dale Peterson and Douglas R. Woodall. Edge-choosability in line-perfect multigraphs. Discrete Mathematics , 202(1--3):191--199, 1999. See also the correction in Discrete Mathematics 260 (2003), 323--326.
  6. Dale Peterson and Douglas R. Woodall. Erratum to ``edge-choosability in line-perfect multigraphs'' [Discrete Mathematics 202 (1999) 191] . Discrete Mathematics , 260(1--3):323--326, 2003.
  7. V. G. Vizing, Coloring the vertices of a graph in prescribed colors (Russian), Diskret.\ Analiz 29 (1976), 3--10.

Version history

  1. v1Submitted by Narayanan NarayananInitial depositCurrentOct 31, 2026