Restricting Odd Antiholes in Critical Graphs via List Coloring
Abstract
By the Strong Perfect Graph Theorem, every graph whose chromatic number exceeds its clique number contains an odd hole or an odd antihole. We investigate the structure of odd antiholes in critical graphs with fixed maximum degree. We prove that if G is a k-critical graph with maximum degree Δ then every odd antihole in G has length at most 2(Δ−k)+7, and conjecture that, in the odd-hole-free setting, equality forces the graph itself to be the corresponding odd antihole. We verify this extremal characterization when Δ≥ 2k−5, extending recent results for Δ=k, and construct k-critical odd-hole-free graphs showing that the next possible odd antihole length 2(Δ−k)+5 below the extremal bound can occur. Our proofs use a list-coloring theorem for graphs on 2ℓ−1 vertices whose complements are hypomatchable. This motivates the conjecture that every odd antihole C2ℓ−1̅ is strongly ℓ-chromatic-choosable; we show that this conjecture would imply the full extremal characterization. We also obtain degree and attachment restrictions for odd antiholes in critical graphs.
Related
- List 3-Coloring in tame classes of graphs in quasipolynomial time
- List coloring C3-free planar graphs with a sparse matching of restricted lists
- Sufficiency of Hall's Condition for Graphic List Coloring
- The List Edge-Coloring Conjecture for New Infinite Families
- Counterexamples to Relaxed Multiplication in List Coloring
BibTeX
@misc{fiujlaali2026restricting,
title = {{Restricting Odd Antiholes in Critical Graphs via List Coloring}},
author = {Alireza Fiujlaali and Jessica McDonald},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.14241},
eprint = {2610.14241},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.14241},
}
RIS
TY - UNPB
TI - Restricting Odd Antiholes in Critical Graphs via List Coloring
AU - Alireza Fiujlaali
AU - Jessica McDonald
PY - 2026
DA - 2026/10/09
PB - arXiv
DO - 10.48550/arxiv.2610.14241
UR - https://arxiv.org/abs/2610.14241
AB - By the Strong Perfect Graph Theorem, every graph whose chromatic number exceeds its clique number contains an odd hole or an odd antihole. We investigate the structure of odd antiholes in critical graphs with fixed maximum degree. We prove that if G is a k-critical graph with maximum degree Δ then every odd antihole in G has length at most 2(Δ−k)+7, and conjecture that, in the odd-hole-free setting, equality forces the graph itself to be the corresponding odd antihole. We verify this extremal characterization when Δ≥ 2k−5, extending recent results for Δ=k, and construct k-critical odd-hole-free graphs showing that the next possible odd antihole length 2(Δ−k)+5 below the extremal bound can occur. Our proofs use a list-coloring theorem for graphs on 2ℓ−1 vertices whose complements are hypomatchable. This motivates the conjecture that every odd antihole C_2ℓ−1̅ is strongly ℓ-chromatic-choosable; we show that this conjecture would imply the full extremal characterization. We also obtain degree and attachment restrictions for odd antiholes in critical graphs.
ER -