Dominating Hadwiger's Conjecture
Dominating Hadwiger's Conjecture
A finite simple graph has a dominating minor if it contains pairwise disjoint non-empty connected subgraphs such that, for every , every vertex in has a neighbor in . A graph is -colorable if its vertices can be partitioned into independent sets.
Dominating Hadwiger's Conjecture. For every integer , every graph with no dominating minor is -colorable.
Illingworth and Wood introduced dominating minors and showed that they coincide with ordinary clique minors for but can differ substantially for . 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 -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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.