Réunion d'hiver SMC 2020

Ottawa, 7 - 11 juin 2021

Prix Coxeter-James
Org: Luke Postle (University of Waterloo)

LUKE POSTLE, University of Waterloo On Hadwiger's Conjecture [PDF]: In 1943, Hadwiger conjectured that every graph with no $K_t$ minor is $(t-1)$-colorable for every $t \ge 1$. Hadwiger's Conjecture is a vast generalization of the Four Color Theorem and one of the most important open problems in graph theory. Only the cases when $t$ is at most 6 are known. In the 1980s, Kostochka and Thomason independently proved that every graph with no $K_t$ minor has average degree $O(t (\log t)^{0.5})$ and hence is $O(t (\log t)^{0.5})$-colorable. In a recent breakthrough, Norin, Song, and I proved that every graph with no $K_t$ minor is $O(t (\log t)^c)$-colorable for every $c > 0.25$, Subsequently I showed that every graph with no $K_t$ minor is $O(t (\log \log t)^6)$-colorable. Delcourt and I improved upon this further by showing that every graph with no $K_t$ minor is $O(t \log \log t)$-colorable. Our main technical result yields this as well as a number of other interesting corollaries. A natural weakening of Hadwiger's Conjecture is the so-called Linear Hadwiger's Conjecture that every graph with no $K_t$ minor is $O(t)$-colorable. We prove that Linear Hadwiger's Conjecture reduces to small graphs. In 2005, Kühn and Osthus proved that Hadwiger's Conjecture for the class of $K_{s,s}$-free graphs for any fixed positive integer $s \ge 2$. Along this line, we show that Linear Hadwiger's Conjecture holds for the class of $K_r$-free graphs for every fixed $r$.