On the choosability of H-minor-free graphs

Abstract

Given a graph H, let us denote by f(chi)(H) and f(l)(H), respectively, the maximum chromatic number and the maximum list chromatic number of H-minor-free graphs. Hadwiger's famous colouring conjecture from 1943 states that f(chi) (K-t) = t - 1 for every t >= 2. A closely related problem that has received significant attention in the past concerns f(l)(K-t), for which it is known that 2t - o(t) < f(l)(K-t) <= O(t(log log t)(6)). Thus, f(l)(K-t) is bounded away from the conjectured value t - 1 for f(chi)(K-t) by at least a constant factor. The socalled H-Hadwiger's conjecture, proposed by Seymour, asks to prove that f(chi)(H) = 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(l)H), thus exploring the limits of a list colouring extension of H-Hadwiger's conjecture. Our main results are: center dot For every epsilon > 0 and all sufficiently large graphs H we have f(l)(H) >= (1 - epsilon)(v(H) + kappa(H)), where kappa(H) denotes the vertex-connectivity of H.center dot For every epsilon > 0 there exists C = C(epsilon) > 0 such that asymptotically almost every n-vertex graph H with [Cn log ni edges satisfies f(l)(H) >= (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 desired value of (v(H) - 1) by a constant factor for all large graphs H of linear connectivity. The second result tells us that for almost all graphs H with superlogarithmic average degree f(l)(H) is separated from (v(H) - 1) by a constant factor arbitrarily close to 2. Conceptually these results indicate that the graphs H for which f(l)(H) is close to the conjectured value (v(H) - 1) for f(chi)(H) are typically rather sparse.