论文标题
当地的哈德威格的猜想
Local Hadwiger's Conjecture
论文作者
论文摘要
我们提出了Hadwiger的猜想的本地版本，其中每个顶点周围只有半径$ω（\ log（v（g）））$的球是$ k_ {t} $ - 次要的。我们问：如果图形是本地的 - $ k_ {t} $ - 少量的，它是否可以$ t $ - 颜色？我们表明，即使在更强的列表颜色设置中，我们的答案是肯定的，我们在本地模型中使用$ O（\ log v（g））$ - 圆形分布式着色算法来补充该结果。此外，我们表明，对于$ t $的足够大值，我们可以在本地列出颜色 - $ k_ {t} $ - $ 13 \ cdot \ cdot \ cdot \ max \ max \ left \ left \ e { $ k_ {t} $ - 次要的图形为$ h（t）$ - 列表上色。我们再次使用$ O（\ log V（g））$ - 圆形分布式算法进行补充。
We propose local versions of Hadwiger's Conjecture, where only balls of radius $Ω(\log(v(G)))$ around each vertex are required to be $K_{t}$-minor-free. We ask: if a graph is locally-$K_{t}$-minor-free, is it $t$-colourable? We show that the answer is yes when $t \leq 5$, even in the stronger setting of list-colouring, and we complement this result with a $O(\log v(G))$-round distributed colouring algorithm in the LOCAL model. Further, we show that for large enough values of $t$, we can list-colour locally-$K_{t}$-minor-free graphs with $13\cdot \max\left\{h(t),\left\lceil \frac{31}{2}(t-1) \right\rceil \right\})$colours, where $h(t)$ is any value such that all $K_{t}$-minor-free graphs are $h(t)$-list-colourable. We again complement this with a $O(\log v(G))$-round distributed algorithm.
