2021/08/03 by Michelle Delcourt, Delcourt, Michelle, Luke Postle +1 · 7 citations
Mathematics · Computer Science · #Limits and Structures in Graph Theory #Advanced Graph Theory Research
paper · pdf · doi:10.48550/arxiv.2108.01633
In 1943, Hadwiger conjectured that every graph with no Kt minor is (t-1)-colorable for every t≥ 1. In the 1980s, Kostochka and Thomason independently proved that every graph with no Kt 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 Kt 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. The first main result of this paper is that every graph with no Kt minor is O(tloglog t)-colorable. This is a corollary of our main technical result that the chromatic number of a Kt-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 Ka-minor-free subgraphs H of G that are small (i.e. O(alog4 a) vertices). This has a number of interesting corollaries. First as mentioned, using the current best-known bounds on coloring small Kt-minor-free graphs, we show that Kt-minor-free graphs are O(tloglog t)-colorable. Second, it shows that proving Linear Hadwiger's Conjecture (that Kt-minor-free graphs are O(t)-colorable) reduces to proving it for small graphs. Third, we prove that Kt-minor-free graphs with clique number at most √(log t)/ (log log t)2 are O(t)-colorable. This implies our final corollary that Linear Hadwiger's Conjecture holds for Kr-free graphs for every fixed r. One key to proving the main theorem is a new standalone result that every Kt-minor-free graph of average degree d=Ω(t) has a subgraph on O(t log3 t) vertices with average degree Ω(d).