Narayanan Narayanan

math.CO — Combinatorics

Claw-free perfect graphs are chromatic-choosable.

Contributed by Narayanan Narayanan, Suchismita Mishra, Umesh Shankar

We prove that every claw-free perfect graph $G$ satisfies $\ch(G)=\chi(G)=\omega(G)$. More strongly, if $S$ is a clique of simplicial vertices of $G$ and $k\ge\omega(G)$, every proper precoloring of $S$ extends to a proper coloring of $G$ from arbitrary lists of size $k$ on $V(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.