On the choosability of $H$-minor-free graphs

Abstract

Given a graph $H$, let us denote by $f_{\ddot{I}}‡(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_{\ddot{I}}‡(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_{\ddot{I}}‡(K_t)$ by at least a constant factor. The so-called $H$-Hadwiger's conjecture, proposed by Seymour, asks to prove that $f_{\ddot{I}}‡(H)=\text{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 $\epsilon >0$ and all sufficiently large graphs $H$ we have $f_{\ell }(H)\ge (1-\epsilon )(\text{v}(H)+\hat{I}º(H))$, where $\hat{I}º(H)$ denotes the vertex-connectivity of $H$. For every $\epsilon >0$ there exists $C=C(\epsilon )>0$ such that asymptotically almost every $n$-vertex graph $H$ with $\lceil Cn\log n\rceil$ edges satisfies $f_{\ell }(H)\ge (2-\epsilon )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 $(\text{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 $(\text{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 $(\text{v}(H)-1)$ are typically rather sparse.

14 pages