Reducing Linear Hadwiger's Conjecture to Coloring Small Graphs
From MaRDI portal
Abstract: In 1943, Hadwiger conjectured that every graph with no minor is -colorable for every . In the 1980s, Kostochka and Thomason independently proved that every graph with no minor has average degree and hence is -colorable. Recently, Norin, Song and the second author showed that every graph with no minor is -colorable for every , making the first improvement on the order of magnitude of the bound. The first main result of this paper is that every graph with no minor is -colorable. This is a corollary of our main technical result that the chromatic number of a -minor-free graph is bounded by where is the maximum of over all and -minor-free subgraphs of that are small (i.e. vertices). This has a number of interesting corollaries. First as mentioned, using the current best-known bounds on coloring small -minor-free graphs, we show that -minor-free graphs are -colorable. Second, it shows that proving Linear Hadwiger's Conjecture (that -minor-free graphs are -colorable) reduces to proving it for small graphs. Third, we prove that -minor-free graphs with clique number at most are -colorable. This implies our final corollary that Linear Hadwiger's Conjecture holds for -free graphs for every fixed . One key to proving the main theorem is a new standalone result that every -minor-free graph of average degree has a subgraph on vertices with average degree .
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)