Local Hadwiger's Conjecture

Abstract

We propose local versions of Hadwiger's Conjecture, where only balls of radius $\Omega (\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\le 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),\lceil \frac{31}{2}(t-1)\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.

25 pages; published in JCTB