๐ฎ
๐ฎ
The Ethereal
Local Hadwiger's Conjecture
March 13, 2022 ยท The Ethereal ยท ๐ J. Comb. Theory B
"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 Contributions
Found the code? Know the venue? Think something is wrong? Let us know!
๐ Similar Papers
In the same crypt โ Combinatorics
๐ฎ
๐ฎ
The Ethereal
On cap sets and the group-theoretic approach to matrix multiplication
๐ฎ
๐ฎ
The Ethereal
Generalized Twisted Gabidulin Codes
๐ฎ
๐ฎ
The Ethereal
Tables of subspace codes
๐ฎ
๐ฎ
The Ethereal
Classification of weighted networks through mesoscale homological features
๐ฎ
๐ฎ
The Ethereal