Reducing Linear Hadwiger's Conjecture to Coloring Small Graphs
share
In 1943, Hadwiger conjectured that every graph with no K_t minor is (t-1)-colorable for every t≥ 1. In the 1980s, Kostochka and Thomason independently proved that every graph with no K_t minor has average degree O(t√(log t)) and hence is O(t√(log t))-colorable. Recently, Norin, Song and the second author showed that every graph with no K_t minor is O(t(log t)^β)-colorable for every β > 1/4, making the first improvement on the order of magnitude of the O(t√(log t)) bound. More recently, the second author showed they are O(t (loglog t)^6)-colorable. Our main technical result is 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 χ(H)/a over all a≥t/√(log t) and K_a-minor-free subgraphs H of G that are small (i.e. O(alog^4 a) vertices). This has a number of interesting corollaries. First, 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. Second, using the current best-known bounds on coloring small K_t-minor-free graphs, we show that K_t-minor-free graphs are O(tloglog t)-colorable. Third, we prove that K_t-minor-free graphs with clique number at most √(log t)/ (loglog t)^2 are O(t)-colorable. This implies our final corollary that Linear Hadwiger's Conjecture holds for K_r-free graphs for any fixed r and sufficiently large t; more specifically, there exists C≥ 1 such that for every r≥ 1, there exists t_r such that for all t≥ t_r, every K_r-free K_t-minor-free graph is Ct-colorable. One key to proving the main theorem is a new standalone result that every K_t-minor-free graph of average degree d=Ω(t) has a subgraph on O(d log^3 t) vertices with average degree Ω(d).
READ FULL TEXT