论文标题
更高的密度增量定理及其在Hadwiger的猜想中的应用
An even better Density Increment Theorem and its application to Hadwiger's Conjecture
论文作者
论文摘要
1943年，哈德威格（Hadwiger）猜想，每张无$ k_t $ binor的图形都是$（t-1）$ - 每$ t \ ge 1 $可着色。在1980年代，Kostochka和Thomason独立证明了每个无$ k_t $ binor的图表的平均度$ O（t \ sqrt {\ log t}）$，因此为$ O（t \ sqrt {\ log log t}）$ - 可着色。最近，Song和作者Norin表明，每张无$ k_t $ binor的图形为$ O（t（\ log t）^β）$ - 每$β> 1/4 $可着色，从而根据$ o（t \ sqrt {\ log t}）的数量级进行第一个改进。最近，作者表明，每个$ k_t $ binor的图形都是$ o（t（\ log t）^β）$ - 每$β> 0 $都可着色；更具体地说，它们是$ t \ cdot 2^{o（（（（\ log \ log \ log t）^{2/3}）}} $ - colorable。结合这项工作，我们在本文中表明，每个图形无$ k_t $ binor是$ o（t（\ log \ log \ log t）^{6}）$ - 可着色。
In 1943, Hadwiger conjectured that every graph with no $K_t$ minor 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. Recently, Norin, Song and the author showed that every graph with no $K_t$ minor is $O(t(\log t)^β)$-colorable for every $β> 1/4$, making the first improvement on the order of magnitude of the $O(t\sqrt{\log t})$ bound. More recently, the author showed that every graph with no $K_t$ minor is $O(t (\log t)^β)$-colorable for every $β> 0$; more specifically, they are $t \cdot 2^{ O((\log \log t)^{2/3}) }$-colorable. In combination with that work, we show in this paper that every graph with no $K_t$ minor is $O(t (\log \log t)^{6})$-colorable.
