Graphs and Matroids Seminar - Luke Postle

Title: Improving the general upper bound for Hadwiger's conjecture

Abstract:

In 1943, Hadwiger conjectured that every K_t-minor-free graph has chromatic number at most t-1. Hadwiger proved his conjecture for t at most 4, while Wagner showed that the t=5 case is equivalent to the Four Color Theorem, which was later proved by Appel and Haken. In 1993, Robertson, Seymour and Thomas proved the conjecture when t=6.

Until recently, the best known upper bound on the chromatic number of K_t-minor-free graphs was O(t (log t)^(1/2)) which follows from the average degree bounds of Kostochka and Thomason. In a recent breakthrough, Norin and Song improved this to O(t (log t)^0.354). 

We improve on their argument by showing that a graph has a small dense subgraph or a minor of desired density in a way that is essentially asymptotically best possible. This result in conjunction with the work of Norin and Song is used to prove an upper bound for the chromatic number of K_t-minor-free graphs of O(t (log t)^(1/4+epsilon)) for any epsilon > 0.