论文标题
图形的连接性和可调性，没有$ k_t $ binor
Connectivity and choosability of graphs with no $K_t$ minor
论文作者
论文摘要
1943年，哈德威格（Hadwiger）猜想，每张无$ k_t $ binor的图形都是$（t-1）$ - 每$ t \ ge 1 $可着色。尽管Hadwiger的猜想不适合列表颜色，但线性削弱的猜想是正确的。在1980年代，Kostochka和Thomason独立证明，每个无$ k_t $ binor的图形都有平均度$ o（t \ sqrt {\ log t}）$，因此是$ o（t \ sqrt {\ log t} {\ log t}）$ - list-list-colorable。最近，作者和歌曲证明，没有$ k_t $ binor的每个图为$ o（t（\ log t）^β）$ - 每$β> \ frac 1 4 $可着色。在这里，我们以此为基础，表明每个无$ k_t $ binor的图形为$ o（t（\ log t）^β）$ - 对于每$β> \ frac 1 4 $都可以列表上色。 我们的主要新工具是高度连接的$ k_t $ -minor-minor-frebragrs中的顶点的上限：我们证明，对于每$β> \ frac 1 4 $，每个$ω（t（\ log t）^β）$连接的图形，没有$ k_t $ o o（t（\ log log t（\ log t）^$ o（\ log t）^$ vertice。
In 1943, Hadwiger conjectured that every graph with no $K_t$ minor is $(t-1)$-colorable for every $t\ge 1$. While Hadwiger's conjecture does not hold for list-coloring, the linear weakening is conjectured to be true. 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 thus is $O(t\sqrt{\log t})$-list-colorable. Recently, the authors and Song proved that every graph with no $K_t$ minor is $O(t(\log t)^β)$-colorable for every $β> \frac 1 4$. Here, we build on that result to show that every graph with no $K_t$ minor is $O(t(\log t)^β)$-list-colorable for every $β> \frac 1 4$. Our main new tool is an upper bound on the number of vertices in highly connected $K_t$-minor-free graphs: We prove that for every $β> \frac 1 4$, every $Ω(t(\log t)^β)$-connected graph with no $K_t$ minor has $O(t (\log t)^{7/4})$ vertices.
