PreprintarXiv licencearXiv
Beyond halfway to Hadwiger's conjecture
Abstract
Hadwiger conjectured in 1943 that every graph with no Kt minor has chromatic number at most t−1. Delcourt and Postle proved that every graph with no Kt minor has chromatic number O(tloglog t). We build on their result to improve this bound to O(tlogloglog t).
Related
BibTeX
@misc{liu2026beyond,
title = {{Beyond halfway to Hadwiger's conjecture}},
author = {Chun-Hung Liu and Jason Luo},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.06867},
eprint = {2609.06867},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.06867},
}
RIS
TY - UNPB
TI - Beyond halfway to Hadwiger's conjecture
AU - Chun-Hung Liu
AU - Jason Luo
PY - 2026
DA - 2026/09/09
PB - arXiv
DO - 10.48550/arxiv.2609.06867
UR - https://arxiv.org/abs/2609.06867
AB - Hadwiger conjectured in 1943 that every graph with no K_t minor has chromatic number at most t−1. Delcourt and Postle proved that every graph with no K_t minor has chromatic number O(tloglog t). We build on their result to improve this bound to O(tlogloglog t).
ER -