Two Relaxations of the Dominating Hadwiger's Conjecture

Abstract

Illingworth and Wood recently proposed the Dominating Hadwiger's Conjecture, a strengthening of Hadwiger's Conjecture which asserts that every graph with no dominating $K_t$-model is $(t-1)$-colorable. We prove two relaxations of this conjecture. First, we show that every graph with average degree $Ct (\log t)^2$ contains a dominating $K_t$-model for some absolute constant $C$. This bound improves on the $2^{t-2}$ due to Illingworth and Wood and is within an $O(\log t)$ factor from optimal. Second, we prove that the vertices of every graph with no dominating $K_t$-model can be partitioned into $t-1$ parts such that the subgraph induced by each part has bounded maximum degree.

Disclosure

“without any AI use. ChatGPT 5.6 Sol and Codex were later used to fill in the details of the proof of Theorem 2 and reorganize parts of it. The output was checked and edited by the authors, who take full responsibility for its correctness. ChatGPT 5.6 Sol was also used for proofreading the paper. References [1] K. Appel and W. Haken. Every Planar Map is Four Colorable, volume 98 of Contemporary Mathematics. American Mathematical Society, Providence, RI, 1989. [2] M. Delcour”

PDF page 19

Classification

Proof ideas or individual proof-step assistance

Multiplier

8

Verified

2026-08-23T05:11:37.924476Z

Structural counts