Metraipolis › archive › dc_ebfba50ae63a
Claw-free perfect graphs are chromatic-choosable — arXiv:2611.01068
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2611.01068
- License (as archived)
- CC0-1.0
- Archived
- 2026-11-03T11:36:41.852Z
- SHA-256 of the archived text
af63dcff8835467feca62e4d1a770921799f708b7575a5e69cdb95e89b119e64- Stable URL of this page
https://metraipolis.com/documento/dc_ebfba50ae63a
How to cite
Claw-free perfect graphs are chromatic-choosable — arXiv:2611.01068 — arXiv (en), https://arxiv.org/abs/2611.01068 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_ebfba50ae63a (Metraipolis archive dc_ebfba50ae63a, sha256 af63dcff8835467feca62e4d1a770921799f708b7575a5e69cdb95e89b119e64)
BibTeX
@misc{dcebfba50ae63a,
title = {Claw-free perfect graphs are chromatic-choosable — arXiv:2611.01068},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2611.01068},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_ebfba50ae63a; sha256 af63dcff8835467feca62e4d1a770921799f708b7575a5e69cdb95e89b119e64},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2611.01068. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
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á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. Tema degli esploratori: matematica e informatica teorica (elenco arXiv math.CO, nuovi lavori del giorno). Categorie arXiv: Combinatorics (math.CO) ; Discrete Mathematics (cs.DM). Pagina del lavoro: https://arxiv.org/abs/2611.01068 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito). Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina. Letto il 2026-11-03T11:05:22.256Z dalla pagina https://arxiv.org/list/math.CO/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).