Reducing Linear Hadwiger's Conjecture to Coloring Small Graphs

From MaRDI portal



Abstract: In 1943, Hadwiger conjectured that every graph with no Kt minor is (t−1)-colorable for every tge1. In the 1980s, Kostochka and Thomason independently proved that every graph with no Kt minor has average degree O(tsqrtlogt) and hence is O(tsqrtlogt)-colorable. Recently, Norin, Song and the second author showed that every graph with no Kt minor is -colorable for every , making the first improvement on the order of magnitude of the O(tsqrtlogt) bound. The first main result of this paper is that every graph with no Kt minor is O(tloglogt)-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 fracchi(H)a over all agefractsqrtlogt and Ka-minor-free subgraphs H of G that are small (i.e. O(alog4a) 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(tloglogt)-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 sqrtlogt/(loglogt)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=Omega(t) has a subgraph on O(tlog3t) vertices with average degree Omega(d).














This page was built for publication: Reducing Linear Hadwiger's Conjecture to Coloring Small Graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6507610)