{
  "id": "2006.11798",
  "version": "v1",
  "published": "2020-06-21T13:33:51.000Z",
  "updated": "2020-06-21T13:33:51.000Z",
  "title": "Further progress towards Hadwiger's conjecture",
  "authors": [
    "Luke Postle"
  ],
  "comment": "16 pages",
  "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 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. Building on that work, we show in this paper that every graph with no $K_t$ minor is $O(t (\\log t)^{\\beta})$-colorable for every $\\beta > 0$; more specifically, they are $t \\cdot 2^{ O((\\log \\log t)^{2/3}) }$-colorable.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2020-06-21T13:33:51.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "hadwigers conjecture",
      "average degree",
      "first improvement"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 16,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}