论文标题
Hadwiger的猜想的精致列表版本
Refined list version of Hadwiger's conjecture
论文作者
论文摘要
假设$λ= \ {k_1，k_2，\ ldots，k_q \} $是$k_λ= \ sum_ {i = 1}^q k_i $的分区。 $ g $的$λ$列表是$k_λ$ list分配$ l $ $ g $的$ g $，使得可以将颜色set $ \ bigcup_ {v \ in v（g）} l（g）} l（v）$可以分配到$ |λ|λ| = q $ sets $ c_1，c_1，c_2，c_2，c_2，c_ $ $ $ $ $， $ | l（v）\ cap c_i | \ ge k_i $。我们说$ g $是\ emph {$λ$ -Choosable}，如果$ g $是$ l $ - 颜色的任何$λ$ list分配$ l $ of $ g $。 $λ$ - 可调用性的概念是可将可塑性的改进，它在同一框架中放置了$ k $ - 可智能和$ k $ - 颜色。如果$ |λ| $接近$k_λ$，则$λ$ -Choosability接近$k_λ$ -colourability;如果$ |λ| $接近$ 1 $，则$λ$ -Choosiability接近$k_λ$ -choosibility。本文研究了Hadwiger在$λ$ - 可智能的背景下的猜想。 Hadwiger的猜想相当于说每个$ k_t $ -minor的图形都是$ \ {1 \ star（t-1）\} $ - 对于任何正整数$ t $都可以选择。我们证明，对于$ t \ ge 5 $，对于$ \ {1 \ star（t-1）\} $以外的任何分区$λ$ $ t-1 $，都有$ k_t $ -minor-minor-free Graph $ g $，而不是$λ$ -Choosable。然后，我们构建了几种类型的$ k_t $ - 不含$λ$ - choosable的图形，其中$k_λ-（t-1）$变大了，因为$k_λ-|λ| $变大。在部分中，对于任何$ q $和任何$ε> 0 $，都存在$ t_0 $，因此对于任何$ t \ ge t_0 $，对于任何分区$λ$ of $ \ lfloor（2-ε）t \ rfloor $ with $ |λ| = q $，有一个$ k_t $ - 最小的图形，不是$λ$ -Choosable。 $ q = 1 $的情况最近由Steiner证明，我们的证明使用了类似的论点。我们还将此结果推广到$（a，b）$ - 列表着色。
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.
