Breaking the degeneracy barrier for coloring graphs with no K minor
Breaking the degeneracy barrier for coloring graphs with no K minor
复制标题
打破无 K 小调着色图的简并障碍
DOI：
10.1016/j.aim.2023.109020
复制
发表时间：
2019
影响因子：
1.7
通讯作者：
Zi
中科院分区：
文献类型：
--
作者：
S. Norin;Zi
在1943年，Hadwiger证明了每个没有Kt子图的图对每个t≥ 1都是（t-1）-可着色的。在20世纪80年代，Kostochka和Kesason独立证明了每个没有Kt子图的图的平均度为O（t log t），因此是O（t log t）-可着色的。我们证明了对于任意β> 1/4，所有不含Kt子图的图都是O（t（log t）β）-可着色的，从而首次改进了Kostochka-Kazason界的数量级.
In 1943, Hadwiger conjectured that every graph with no K t minor is (t− 1)-colorable for every t≥ 1. In the 1980s, Kostochka and Thomason independently proved that every graph with no K t minor has average degree O (t log t) and hence is O (t log t)-colorable. We show 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 Kostochka-Thomason bound.