论文标题
改进的绑定，不正确的图形，没有奇数集团
Improved bound for improper colorings of graphs with no odd clique minor
论文作者
论文摘要
加强了Hadwiger的猜想，Gerards和Seymour在1995年提出的，每个图表都没有奇数$ k_t $ -minor的适当$（T-1）$ - 可着色，这被称为奇怪的Hadwiger的猜想。我们证明了上述猜想的放松，也就是说，每个没有奇数$ k_t $ -minor的图形都承认一个顶点$（2T-2）$ - 颜色，使所有单色组件最多都有$ \ lceil \ frac \ frac {1} {1} {1} {2} {2}（t-2}（t-2}（t-2）\ rceil $。颜色的界限最佳达到$ 2 $，Kawarabayashi（2008），Kang and Oum（2019），Liu和Wood（2021）提高了以前的界限，并增强了Van Den Heuvel和Wood（2018）的结果，这些结论显示了上述结论更加限制了该图的$ k_ $ k_ $ k的$ kin是$ k的。此外，在我们的结果中，组件大小的界限远小于以前的结果，在这种结果中，对$ t $的依赖性不明显。我们的简短证明将Van Den Heuvel和Wood的方法结合在一起，$ k_t $ -minor的免费图形以及一些其他想法，这使得扩展到奇数$ k_t $ -minor免费图形。
Strengthening Hadwiger's conjecture, Gerards and Seymour conjectured in 1995 that every graph with no odd $K_t$-minor is properly $(t-1)$-colorable, this is known as the Odd Hadwiger's conjecture. We prove a relaxation of the above conjecture, namely we show that every graph with no odd $K_t$-minor admits a vertex $(2t-2)$-coloring such that all monochromatic components have size at most $\lceil \frac{1}{2}(t-2) \rceil$. The bound on the number of colors is optimal up to a factor of $2$, improves previous bounds for the same problem by Kawarabayashi (2008), Kang and Oum (2019), Liu and Wood (2021), and strengthens a result by van den Heuvel and Wood (2018), who showed that the above conclusion holds under the more restrictive assumption that the graph is $K_t$-minor free. In addition, the bound on the component-size in our result is much smaller than those of previous results, in which the dependency on $t$ was non-explicit. Our short proof combines the method by van den Heuvel and Wood for $K_t$-minor free graphs with some additional ideas, which make the extension to odd $K_t$-minor free graphs possible.
