{
  "id": "2108.01633",
  "version": "v1",
  "published": "2021-08-03T17:09:29.000Z",
  "updated": "2021-08-03T17:09:29.000Z",
  "title": "Reducing Linear Hadwiger's Conjecture to Coloring Small Graphs",
  "authors": [
    "Michelle Delcourt",
    "Luke Postle"
  ],
  "comment": "23 pages. arXiv admin note: text overlap with arXiv:2006.11798, arXiv:2010.05999",
  "categories": [
    "math.CO",
    "cs.DM"
  ],
  "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. More recently, the second author showed they are $O(t (\\log \\log 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 $\\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, 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(t\\log\\log t)$-colorable. 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 any fixed $r$ and sufficiently large $t$; more specifically, 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 a new standalone result that every $K_t$-minor-free graph of average degree $d=\\Omega(t)$ has a subgraph on $O(d \\log^3 t)$ vertices with average degree $\\Omega(d)$.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2021-08-03T17:09:29.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C15",
      "05C83"
    ],
    "keywords": [
      "reducing linear hadwigers conjecture",
      "minor-free graph",
      "coloring small graphs",
      "average degree",
      "linear hadwigers conjecture holds"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 23,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}