{"id":"arxiv/2608.12126","url":"https://arxiv.org/abs/2608.12126","tags":["math.CO"],"score":0,"title":"Two Relaxations of the Dominating Hadwiger's Conjecture","domain":"math.CO","source":"arxiv","authors":["António Girão","Sergey Norin","Youri Tamitegama","Jane Tan"],"reviews":0,"subject":"math.CO","summary":"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…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-08-12","reactions":{}}