PreprintCC BY 4.0arXiv
A shorter proof of the linear list Hadwiger conjecture
Abstract
The linear list Hadwiger conjecture asserts that every Kt-minor-free graph is O(t)-choosable. Following an approach outlined by Delcourt and Postle, we recently established O(tloglog t)-choosability. Soon afterward, OpenAI provided a proof of the conjecture. A key new ingredient of their proof is a linear bound on the choice number of Kt-minor-free graphs with at most t11/10 vertices. In this paper, we give a relatively simple proof of this small-graph bound for graphs with at most t(ln t)5 vertices.Combining this with the argument from our earlier O(tloglog t) bound, we obtain a shorter and somewhat more accessible proof of the conjecture.
Related
- A Proof of the Linear Hadwiger Conjecture
- Beyond halfway to Hadwiger's conjecture
- Integer decomposition property of three-dimensional smooth polytopes: a shorter proof
- Fractional illumination and the optimal exponential rate in Hadwiger's covering conjecture
- Shorter proof of dimension-free Lp estimates for maximal Riesz transforms
BibTeX
@misc{gu2026shorter,
title = {{A shorter proof of the linear list Hadwiger conjecture}},
author = {Yangyan Gu and Rongxing Xu},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.01946},
eprint = {2610.01946},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.01946},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - A shorter proof of the linear list Hadwiger conjecture
AU - Yangyan Gu
AU - Rongxing Xu
PY - 2026
DA - 2026/10/12
PB - arXiv
DO - 10.48550/arxiv.2610.01946
UR - https://arxiv.org/abs/2610.01946
AB - The linear list Hadwiger conjecture asserts that every K_t-minor-free graph is O(t)-choosable. Following an approach outlined by Delcourt and Postle, we recently established O(tloglog t)-choosability. Soon afterward, OpenAI provided a proof of the conjecture. A key new ingredient of their proof is a linear bound on the choice number of K_t-minor-free graphs with at most t^11/10 vertices. In this paper, we give a relatively simple proof of this small-graph bound for graphs with at most t(ln t)^5 vertices.Combining this with the argument from our earlier O(tloglog t) bound, we obtain a shorter and somewhat more accessible proof of the conjecture.
ER -