Local Hadwiger's Conjecture

March 13, 2022 ยท The Ethereal ยท ๐Ÿ› J. Comb. Theory B

๐Ÿ”ฎ THE ETHEREAL: The Ethereal
Pure theory โ€” exists on a plane beyond code

"No code URL or promise found in abstract"

Evidence collected by the PWNC Scanner

Authors Benjamin Moore, Luke Postle, Lise Turner arXiv ID 2203.06718 Category math.CO: Combinatorics Cross-listed cs.DC, cs.DS Citations 0 Venue J. Comb. Theory B Last Checked 3 months ago
Abstract
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.
Community shame:
Not yet rated
Community Contributions

Found the code? Know the venue? Think something is wrong? Let us know!

๐Ÿ“œ Similar Papers

In the same crypt โ€” Combinatorics

๐Ÿ”ฎ ๐Ÿ”ฎ The Ethereal

Tables of subspace codes

Daniel Heinlein, Michael Kiermaier, ... (+2 more)

math.CO ๐Ÿ› arXiv ๐Ÿ“š 94 cites 10 years ago