{
  "id": "2004.10367",
  "version": "v1",
  "published": "2020-04-22T01:58:10.000Z",
  "updated": "2020-04-22T01:58:10.000Z",
  "title": "Connectivity and choosability of graphs with no $K_t$ minor",
  "authors": [
    "Sergey Norin",
    "Luke Postle"
  ],
  "categories": [
    "math.CO"
  ],
  "abstract": "In 1943, Hadwiger conjectured that every graph with no $K_t$ minor is $(t-1)$-colorable for every $t\\ge 1$. While Hadwiger's conjecture does not hold for list-coloring, the linear weakening is conjectured to be true. 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 thus is $O(t\\sqrt{\\log t})$-list-colorable. Recently, the authors and Song proved that every graph with no $K_t$ minor is $O(t(\\log t)^{\\beta})$-colorable for every $\\beta > \\frac 1 4$. Here, we build on that result to show that every graph with no $K_t$ minor is $O(t(\\log t)^{\\beta})$-list-colorable for every $\\beta > \\frac 1 4$. Our main new tool is an upper bound on the number of vertices in highly connected $K_t$-minor-free graphs: We prove that for every $\\beta > \\frac 1 4$, every $\\Omega(t(\\log t)^{\\beta})$-connected graph with no $K_t$ minor has $O(t (\\log t)^{7/4})$ vertices.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2020-04-22T01:58:10.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "connectivity",
      "choosability",
      "hadwigers conjecture",
      "average degree",
      "upper bound"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}