Dominating Hadwiger's Conjecture

A finite simple graph GG has a dominating KtK_t minor if it contains pairwise disjoint non-empty connected subgraphs (T1,,Tt)(T_1,\ldots,T_t) such that, for every 1i<jt1\leq i<j\leq t, every vertex in TjT_j has a neighbor in TiT_i. A graph is (t1)(t-1)-colorable if its vertices can be partitioned into t1t-1 independent sets.

Dominating Hadwiger's Conjecture. For every integer t1t\geq 1, every graph with no dominating KtK_t minor is (t1)(t-1)-colorable.

Illingworth and Wood introduced dominating minors and showed that they coincide with ordinary clique minors for t3t\leq 3 but can differ substantially for t=4t=4. Norin referred to this as the Dominating Hadwiger's Conjecture and suspected it was false; the paper under consideration proves that it holds for all 2K22K_2-free graphs.

Sources & referencesView supporting material

Primary source

Zi-Xia Song and Thomas Tibbetts, “Dominating Hadwiger's Conjecture holds for all 2K_2-free graphs”, arXiv:2510.12567 (2025).

Additional references

2 papers in this index state this conjecture (2025). The statement above is taken from the most recent of them; the others are arXiv:2510.12564.

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.