{
  "id": "2304.04246",
  "version": "v1",
  "published": "2023-04-09T14:30:05.000Z",
  "updated": "2023-04-09T14:30:05.000Z",
  "title": "On the choosability of $H$-minor-free graphs",
  "authors": [
    "Olivier Fischer",
    "Raphael Steiner"
  ],
  "comment": "14 pages",
  "categories": [
    "math.CO"
  ],
  "abstract": "Given a graph $H$, let us denote by $f_\\chi(H)$ and $f_\\ell(H)$, respectively, the maximum chromatic number and the maximum list chromatic number of $H$-minor-free graphs. Hadwiger's famous coloring conjecture from 1943 states that $f_\\chi(K_t)=t-1$ for every $t \\ge 2$. In contrast, for list coloring it is known that $2t-o(t) \\le f_\\ell(K_t) \\le O(t (\\log \\log t)^6)$ and thus, $f_\\ell(K_t)$ is bounded away from the conjectured value $t-1$ for $f_\\chi(K_t)$ by at least a constant factor. The so-called $H$-Hadwiger's conjecture, proposed by Seymour, asks to prove that $f_\\chi(H)=\\textsf{v}(H)-1$ for a given graph $H$ (which would be implied by Hadwiger's conjecture). In this paper, we prove several new lower bounds on $f_\\ell(H)$, thus exploring the limits of a list coloring extension of $H$-Hadwiger's conjecture. Our main results are: For every $\\varepsilon>0$ and all sufficiently large graphs $H$ we have $f_\\ell(H)\\ge (1-\\varepsilon)(\\textsf{v}(H)+\\kappa(H))$, where $\\kappa(H)$ denotes the vertex-connectivity of $H$. For every $\\varepsilon>0$ there exists $C=C(\\varepsilon)>0$ such that asymptotically almost every $n$-vertex graph $H$ with $\\left\\lceil C n\\log n\\right\\rceil$ edges satisfies $f_\\ell(H)\\ge (2-\\varepsilon)n$. The first result generalizes recent results on complete and complete bipartite graphs and shows that the list chromatic number of $H$-minor-free graphs is separated from the natural lower bound $(\\textsf{v}(H)-1)$ by a constant factor for all large graphs $H$ of linear connectivity. The second result tells us that even when $H$ is a very sparse graph (with an average degree just logarithmic in its order), $f_\\ell(H)$ can still be separated from $(\\textsf{v}(H)-1)$ by a constant factor arbitrarily close to $2$. Conceptually these results indicate that the graphs $H$ for which $f_\\ell(H)$ is close to $(\\textsf{v}(H)-1)$ are typically rather sparse.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2023-04-09T14:30:05.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C15",
      "05C80",
      "05C83"
    ],
    "keywords": [
      "minor-free graphs",
      "hadwigers conjecture",
      "constant factor",
      "maximum list chromatic number",
      "large graphs"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 14,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}