Disproof of the dominating Hadwiger conjecture

Abstract

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,\dots,T_t$ such that for all $1\le i<j\le 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.