TOPICS
Search

Dominating Hadwiger Conjecture

A dominating K_t-model in a graph G is an ordered tuple (T_1,...,T_t) of pairwise vertex-disjoint connected subgraphs such that, whenever i<j, every graph vertex of T_j has a neighbor in T_i. The dominating Hadwiger conjecture asserted that every graph G with chromatic number at least t contains a dominating K_t-model.

Illingworth and Steiner (2026) disproved the conjecture. They proved that there is an absolute constant delta>0 such that, for every sufficiently large odd integer m, there is a graph G on N=16^m vertices with independence number

alpha(G)<=2

but containing no dominating K_([(1/2-delta)N])-model. Since its chromatic number satisfies chi(G)>=N/2, this graph is a counterexample. The construction takes the graph complement of a pseudorandom triangle-free graph obtained by randomly subsampling a block-geometric construction based on the Suzuki-Tits ovoid.

Illingworth and Steiner (2026) state that GPT-6 Astra Ultra found the disproof after being directed toward complements of suitable triangle-free graphs and related constructions. The authors checked the proof and take responsibility for its correctness.

See also

Chromatic Number, Graph Minor, Hadwiger Conjecture

Explore with Wolfram|Alpha

References

Illingworth, F. and Steiner, R. "Disproof of the Dominating Hadwiger Conjecture." 28 Sep 2026. https://arxiv.org/abs/2609.35361.

Cite this as:

Weisstein, Eric W. "Dominating Hadwiger Conjecture." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/DominatingHadwigerConjecture.html

Subject classifications