Recent Progress on Hadwiger's Conjecture

Abstract: 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 graphs (provided $t$ is sufficiently large). This is joint work with Luke Postle.

combinatorics

Audience: researchers in the topic

Warwick Combinatorics Seminar

Series comments: This is the online combinatorics seminar at Warwick.