Title: A local version of Hadwiger’s Conjecture
|Affiliation:||University of Waterloo|
|Zoom:||http://matroidunion.org/?page_id=2477 or contact Shayla Redlin|
In 1943, Hadwiger famously conjectured that graphs with no $K_t$ minors are $t-1$ colourable. There has also been significant interest in several variants of the problem, such as list colouring or only forbidding certain classes of minors. We propose a local version where all balls of radius $O(\log v(G))$ must be $K_t$-minor free but the graph as a whole may not be. We prove list colouring results for these graphs equivalent to the best known results for $K_t$-minor free graphs for $t\leq 5$ and large $t$. In the process, we provide some efficient distributed algorithms for finding such colourings.
Joint work with Benjamin Moore and Luke Postle.