Seminar: Recent Progress on Hadwiger's Conjecture

In 1943, Hadwiger conjectured that every graph with no $K_t$ minor is $(t-1)$-colorable for every $t \ge 1$.  In a recent breakthrough, Norin, Song, and Postle proved that every graph with no $K_t$ minor is $O(t (\log t)^c)$-colorable for every $c > 0.25$,  Subsequently Postle showed that every graph with no $K_t$ minor is $O(t (\log \log t)^6)$-colorable.  We improve upon this further 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 as well as that Linear Hadwiger's Conjecture holds for the class of $K_r$-free $K_t$-minor-free graphs (provided $t$ is sufficiently large).  This is joint work with Luke Postle.