Claw-free perfect graphs have matching color and list color numbers
Claw-free perfect graphs are chromatic-choosable
Discrete Mathematics
Summary
Coloring a graph means assigning colors to points so that connected points are different colors. Some graphs are tricky to color even when you have lists of allowed colors for each point. The authors prove that for a special kind of graphs called claw-free perfect graphs, the minimum number of colors needed matches the hard case when colors come from lists. This helps solve an older puzzle about extending colors from a small group to the whole graph and shows this property for all perfect line graphs too.
What this means in practice
- •For graph algorithm designers: Use the result that list coloring matches chromatic number for claw-free perfect graphs to simplify algorithms for graph coloring with constraints.
- •For network schedulers: Optimize resource assignments in networks modeled by claw-free perfect graphs knowing precolorings can extend efficiently to full schedules with given constraints.
A theory result. No direct application yet.
Authors
Suchismita Mishra, Narayanan Narayanan, Umesh Shankar
Abstract
We prove that every claw-free perfect graph $G$ satisfies $\ch(G)=χ(G)=ω(G)$. More strongly, if $S$ is a clique of simplicial vertices of $G$ and $k\geω(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átal--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.