论文标题
朝哈德威格的猜想进一步发展
Further progress towards 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 $可着色。更具体地说，与作者的另一篇论文结合，它们是$ o（t \ cdot（\ log \ log t）^{18}）$ - 可颜色。
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. Building on that work, we show in this paper that every graph with no $K_t$ minor is $O(t (\log t)^β)$-colorable for every $β> 0$. More specifically in conjunction with another paper by the author, they are $O(t \cdot (\log \log t)^{18})$-colorable.
