Reducing linear Hadwiger’s conjecture to coloring small graphs

Abstract:

In 1943, Hadwiger conjectured that every graph with no $K_t$ minor is $(t-1)$-colorable for every $t\ge 1$. In the 1980s, Kostochka and Thomason independently proved that every graph with no $K_t$ minor has average degree $O(t\sqrt {\log t})$ and hence is $O(t\sqrt {\log t})$-colorable. Recently, Norin, Song and the second author showed that every graph with no $K_t$ minor is $O(t(\log t)^{\beta })$-colorable for every $\beta > 1/4$, making the first improvement on the order of magnitude of the $O(t\sqrt {\log t})$ bound. The first main result of this paper is that every graph with no $K_t$ minor is $O(t\log \log t)$-colorable.

This is actually a corollary of our main technical result that the chromatic number of a $K_t$-minor-free graph is bounded by $O(t(1+f(G,t)))$ where $f(G,t)$ is the maximum of $\frac {\chi (H)}{a}$ over all $a\ge \frac {t}{\sqrt {\log t}}$ and $K_a$-minor-free subgraphs $H$ of $G$ that are small (i.e. $O(a\log ^4 a)$ vertices). This has a number of interesting corollaries. First as mentioned, using the current best-known bounds on coloring small $K_t$-minor-free graphs, we show that $K_t$-minor-free graphs are $O(t\log \log t)$-colorable. Second, it shows that proving Linear Hadwiger’s Conjecture (that $K_t$-minor-free graphs are $O(t)$-colorable) reduces to proving it for small graphs. Third, we prove that $K_t$-minor-free graphs with clique number at most $\sqrt {\log t}/ (\log \log t)^2$ are $O(t)$-colorable. This implies our final corollary that Linear Hadwiger’s Conjecture holds for $K_r$-free graphs for every fixed $r$; more generally, we show there exists $C\ge 1$ such that for every $r\ge 1$, there exists $t_r$ such that for all $t\ge t_r$, every $K_r$-free $K_t$-minor-free graph is $Ct$-colorable.

One key to proving the main theorem is building the minor in two new ways according to whether the chromatic number ‘separates’ in the graph: sequentially if the graph is the chromatic-inseparable and recursively if the graph is chromatic-separable. The other key is a new standalone result that every $K_t$-minor-free graph of average degree $d=\Omega (t)$ has a subgraph on $O(t \log ^3 t)$ vertices with average degree $\Omega (d)$.