CoxeterJames Prize
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 $(t1)$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 socalled 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$.