Recent progress towards 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$. Hadwiger’s conjecture generalizes the Four Color Theorem and is among most studied problems in graph theory.

In this paper we survey the ideas behind recent progress towards this conjecture, which, in particular, allowed for the first asymptotic improvement since 1980s on the number of colors sufficient to color every graph with no $K_t$ minor.