In 1943, Hadwiger conjectured that every $K_t$-minor-free graph is $(t-1)$-colorable for every $t\ge 1$. In the 1980s, Kostochka and Thomason independently proved that every graph with no $K_t$ minor has average degree $O(t\sqrt{\log t})$ and hence is $O(t\sqrt{\log t})$-colorable. Very recently, Norin and Song proved that every graph with no $K_t$ minor is $O(t(\log t)^{0.354})$-colorable. Improving on the second part of their argument, we prove that every graph with no $K_t$ minor is $O(t(\log t)^{\beta})$-colorable for every $\beta > \frac{1}{4}$.
翻译:1943年,哈德维格推测,每张K$ t$-minor-final 图形每张K$(t-1)-color $1美元。在1980年代,科斯托奇卡和托马松独立地证明,每张没有K$-t$(t)的图均具有O(t\sqrt_log t})美元,因此是$O(t\sqrt_log t})-colorable。最近,诺林和宋证明,每张没有K_t$(t) $(t) $(t) ⁇ 0. 354} 美元($)的图均具有色度。在他们的论点第二部分中,我们改进了他们的论证,我们证明每张没有K_t$(t)的图均具有O(t(t) t(t\log t) { ⁇ _beta) $($-colorable for $ >\ frac{%4}。