























Assume $λ=\{k_1,k_2, \ldots, k_q\}$ is a partition of $k_λ = \sum_{i=1}^q k_i$. A $λ$-list assignment of $G$ is a $k_λ$-list assignment $L$ of $G$ such that the colour set $\bigcup_{v \in V(G)}L(v)$ can be partitioned into $|λ|= q$ sets $C_1,C_2,\ldots,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{$λ$-choosable} if $G$ is $L$-colourable for any $λ$-list assignment $L$ of $G$. The concept of $λ$-choosability is a refinement of choosability that puts $k$-choosability and $k$-colourability in the same framework. If $|λ|$ is close to $k_λ$, then $λ$-choosability is close to $k_λ$-colourability; if $|λ|$ is close to $1$, then $λ$-choosability is close to $k_λ$-choosability. This paper studies Hadwiger's Conjecture in the context of $λ$-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 $λ$ of $t-1$ other than $\{1 \star (t-1)\}$, there is a $K_t$-minor-free graph $G$ that is not $λ$-choosable. We then construct several types of $K_t$-minor-free graphs that are not $λ$-choosable, where $k_λ- (t-1)$ gets larger as $k_λ-|λ|$ gets larger. In partcular, for any $q$ and any $ε> 0$, there exists $t_0$ such that for any $t \ge t_0$, for any partition $λ$ of $\lfloor (2-ε)t \rfloor$ with $|λ| =q$, there is a $K_t$-minor-free graph that is not $λ$-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.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。