For every integer t≥ 1 and every graph G with chi(G)≥ t, there exist pairwise vertex-disjoint connected subgraphs T_1,…,T_t such that, for every pair 1≤ i<j≤ t and every vertex v∈ V(T_j), the vertex v has a neighbor in T_i. Such a collection is called a dominating K_t-model.

Dominating Hadwiger conjecture

The conjecture asks whether every graph with chromatic number at least $t$ contains a dominating $K_t$ -model. Illingworth and Wood introduced the notion; Norin later named the conjecture and reportedly suspected it was false.

Known results

The conjecture was proved for $t=4$ by Illingworth and Wood.
Every graph with no dominating $K_5$ -model is $4$ -colorable (Norin; later reported as “The Dominating 4-Colour Theorem”).
It holds for all $2K_2$ -free graphs.
Average degree $C t(\log t)^2$ guarantees a dominating $K_t$ -model, a substantial relaxation of the conjecture.

September 28, 2026 claimed disproof

Freddie Illingworth and Raphael Steiner’s new preprint claims a construction showing that chromatic number at least $t$ need not force a dominating $K_t$ -model, which would refute the conjecture. The authors describe the construction as found by ChatGPT 6 Astra Ultra; the mathematical claim remains unverified.

Current status (as of September 2026): Earlier special cases and relaxations are established, while a new preprint claims a counterexample to the full conjecture; that disproof remains unverified.

Dominating Hadwiger conjecture

Primary source

Additional references

Progress summary

Solutions 0