Albertson's Conjecture for Chromatic Numbers at Most 29
Abstract
Albertson's conjecture asserts that every finite simple graph G with χ(G) ≥ r satisfies cr(G) ≥ cr(Kr). Building on Cranston's verification for r ≤ 24 and his reduction of r ∈ {25,26} to three residual orders, we eliminate those residual cases and then prove the cases r=27,28,29. The first structural ingredient is a Kempe-chain construction: if a k-critical graph has a vertex of degree k−1, then it contains a branch-clean essential immersion of Kk. Essential immersions are crossing-monotone, so a critical counterexample must have minimum degree at least k. For r=27, this one-unit degree gain, Gallai's join structure, critical-graph edge bounds, and induced-subgraph averaging close every possible order. For r=28 and r=29, the remaining near-2r orders are converted to dense complements. Stehlík's coloring theorem makes the odd-order complements factor-critical; a clique-partition obstruction yields an anti-tight matching property; and Tutte barriers, Hall-type expansion, and deficit bookkeeping eliminate the final cases. At order 58 for r=29, Rabern's coloring inequality handles the regular case, while the last degree-deficit-two case is reduced to two disjoint triangles and a finite barrier analysis.
Related
- A Proof of Albertson's Conjecture
- Treewidth and the Product of Tree-Independence and Tree-Chromatic Numbers
- Improved bounds on the b-chromatic number using the independence and chromatic numbers
- Bounds on the maximum denominator of fractional chromatic numbers
- Clique and chromatic numbers of graph powers: spectral bounds and anticodes
BibTeX
@misc{cao2026albertsons,
title = {{Albertson's Conjecture for Chromatic Numbers at Most 29}},
author = {Sen Cao and Sanjit Singh Mehat},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.04771},
eprint = {2609.04771},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.04771},
}
RIS
TY - UNPB
TI - Albertson's Conjecture for Chromatic Numbers at Most 29
AU - Sen Cao
AU - Sanjit Singh Mehat
PY - 2026
DA - 2026/09/04
PB - arXiv
DO - 10.48550/arxiv.2609.04771
UR - https://arxiv.org/abs/2609.04771
AB - Albertson's conjecture asserts that every finite simple graph G with χ(G) ≥ r satisfies cr(G) ≥ cr(K_r). Building on Cranston's verification for r ≤ 24 and his reduction of r ∈ {25,26} to three residual orders, we eliminate those residual cases and then prove the cases r=27,28,29. The first structural ingredient is a Kempe-chain construction: if a k-critical graph has a vertex of degree k−1, then it contains a branch-clean essential immersion of K_k. Essential immersions are crossing-monotone, so a critical counterexample must have minimum degree at least k. For r=27, this one-unit degree gain, Gallai's join structure, critical-graph edge bounds, and induced-subgraph averaging close every possible order. For r=28 and r=29, the remaining near-2r orders are converted to dense complements. Stehlík's coloring theorem makes the odd-order complements factor-critical; a clique-partition obstruction yields an anti-tight matching property; and Tutte barriers, Hall-type expansion, and deficit bookkeeping eliminate the final cases. At order 58 for r=29, Rabern's coloring inequality handles the regular case, while the last degree-deficit-two case is reduced to two disjoint triangles and a finite barrier analysis.
ER -