Skip to content
DraconiticResearch
Search Sources API
201,818 studies31 sourcesUpdated 25 min ago
PreprintCC BY 4.0arXiv

Disproof of the dominating Hadwiger conjecture

  • Freddie Illingworth
  • Raphael Steiner
Open at sourcePDFDOICite

Abstract

Hadwiger's conjecture (1943) states that every graph G with chromatic number at least t contains a Kt-model: a collection of t vertex-disjoint connected subgraphs T1,…,Tt such that for all 1≤ i<j≤ t some vertex in Tj has a neighbour in Ti. Replacing "some" in this definition by "every" gives rise to the significantly stronger notion of a dominating Kt-model introduced by Illingworth and Wood (2024). They raised the question whether every graph of chromatic number at least t contains a dominating Kt-model. This statement is a significant strengthening of Hadwiger's conjecture and has come to be known as the dominating Hadwiger conjecture. We provide our own exposition of a disproof of this conjecture found by ChatGPT 6 Astra Ultra. The construction is the complement of a pseudorandom triangle-free graph that is obtained by randomly subsampling a block geometric graph based on the Suzuki-Tits ovoid.

Related

  1. Remarks on the disproof of the unit distance conjecture
    Noga Alon, Thomas F. Bloom, W. T. Gowers +6
    arXiv (Cornell University)PreprintCC BYFull text84 citedCombinatorics & discrete mathematicsOpenAlex
  2. A Proof of the Linear Hadwiger Conjecture
    Sergey Norin, Raphael Steiner
    arXivPreprintCC BY-NC-SA 4.0Full textCombinatorics & discrete mathematicsarXiv
  3. Beyond halfway to Hadwiger's conjecture
    Chun-Hung Liu, Jason Luo
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  4. Fractional illumination and the optimal exponential rate in Hadwiger's covering conjecture
    Yegor Gorodzha
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsGeometry & topologyarXiv
  5. On a classical zero-sum invariant II: Disproof of a long-standing conjecture
    Alfred Geroldinger, Guoqing Wang, Wenkai Yang
    arXivPreprintCC BY 4.0Full textAlgebra & number theoryCombinatorics & discrete mathematicsarXiv

Cite

BibTeXRIS
BibTeX
@misc{illingworth2026disproof,
  title = {{Disproof of the dominating Hadwiger conjecture}},
  author = {Freddie Illingworth and Raphael Steiner},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2609.35361},
  eprint = {2609.35361},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.35361},
  note = {CC BY 4.0},
}
RIS
TY  - UNPB
TI  - Disproof of the dominating Hadwiger conjecture
AU  - Freddie Illingworth
AU  - Raphael Steiner
PY  - 2026
DA  - 2026/09/28
PB  - arXiv
DO  - 10.48550/arxiv.2609.35361
UR  - https://arxiv.org/abs/2609.35361
AB  - Hadwiger's conjecture (1943) states that every graph G with chromatic number at least t contains a K_t-model: a collection of t vertex-disjoint connected subgraphs T_1,…,T_t such that for all 1≤ i<j≤ t some vertex in T_j has a neighbour in T_i. Replacing "some" in this definition by "every" gives rise to the significantly stronger notion of a dominating K_t-model introduced by Illingworth and Wood (2024). They raised the question whether every graph of chromatic number at least t contains a dominating K_t-model. This statement is a significant strengthening of Hadwiger's conjecture and has come to be known as the dominating Hadwiger conjecture. We provide our own exposition of a disproof of this conjecture found by ChatGPT 6 Astra Ultra. The construction is the complement of a pseudorandom triangle-free graph that is obtained by randomly subsampling a block geometric graph based on the Suzuki-Tits ovoid.
ER  -