Refined list version of Hadwiger's conjecture

Abstract

Assume $\lambda =\{k_1,k_2,\dots ,k_q\}$ is a partition of $k_{\lambda }={\sum }_{i=1}^q{k}_i$. A $\lambda$-list assignment of $G$ is a $k_{\lambda }$-list assignment $L$ of $G$ such that the colour set ${\bigcup }_{v\in V(G)}L(v)$ can be partitioned into $|\lambda |=q$ sets $C_1,C_2,\dots ,C_q$ such that for each $i$ and each vertex $v$ of $G$, $|L(v)\cap C_i|\ge k_i$. We say $G$ is \emph{$\lambda$-choosable} if $G$ is $L$-colourable for any $\lambda$-list assignment $L$ of $G$. The concept of $\lambda$-choosability is a refinement of choosability that puts $k$-choosability and $k$-colourability in the same framework. If $|\lambda |$ is close to $k_{\lambda }$, then $\lambda$-choosability is close to $k_{\lambda }$-colourability; if $|\lambda |$ is close to $1$, then $\lambda$-choosability is close to $k_{\lambda }$-choosability. This paper studies Hadwiger's Conjecture in the context of $\lambda$-choosability. Hadwiger's Conjecture is equivalent to saying that every $K_t$-minor-free graph is $\{1\star (t-1)\}$-choosable for any positive integer $t$. We prove that for $t\ge 5$, for any partition $\lambda$ of $t-1$ other than $\{1\star (t-1)\}$, there is a $K_t$-minor-free graph $G$ that is not $\lambda$-choosable. We then construct several types of $K_t$-minor-free graphs that are not $\lambda$-choosable, where $k_{\lambda }-(t-1)$ gets larger as $k_{\lambda }-|\lambda |$ gets larger. In partcular, for any $q$ and any $\epsilon >0$, there exists $t_0$ such that for any $t\ge t_0$, for any partition $\lambda$ of $\lfloor (2-\epsilon )t\rfloor$ with $|\lambda |=q$, there is a $K_t$-minor-free graph that is not $\lambda$-choosable. The $q=1$ case of this result was recently proved by Steiner, and our proof uses a similar argument. We also generalize this result to $(a,b)$-list colouring.