论文标题
最小非chrostic- $λ$ -Choosable图
Minimum non-chromatic-$λ$-choosable graphs
论文作者
论文摘要
对于多组$λ= \ {k_1，k_2，\ ldots，k_q \} $的正整数，让$k_λ= \ sum_ {i = 1}^q k_i $。 $ g $的$λ$列表是$ g $的列表分配$ l $ $ g $，使得可以将颜色集$ \ bigCup_ {v \ in v（g）} l（v）$可以分配到Discoint $ c_1 \ c_1 \ cup c_1 \ cup c_2 \ c_2 \ cup c_2 \ cup \ ldots \ ldots \ c_q $ $ q $ g $ g $ g $ g $ i g i g y $ $ | l（v）\ cap c_i | \ ge k_i $。我们说，如果$ g $是$ l $ - 颜色的，对于任何$λ$ list tistment $ l $ l $ of $ g $，则$ g $是$λ$ -Choosable。 $λ$ -Choosability的概念将$ k $ - 颜色性和$ k $ -choosability在同一框架中：如果$λ= \ {k \} $，则$λ$ - choosiability等于$ k $ -Choosability;如果$λ$由$ 1 $ $ 1 $的$ k $组成，则$λ$ - 可调用性等效于$ k $ - 颜色。如果$ g $是$λ$ - choosable，则$ g $是$k_λ$ - 颜色。另一方面，只要$λ$包含大于$ 1 $的整数，就有$k_λ$ - 颜色的图形。令$ ϕ（λ）$为$k_λ$ -olourable的非$ $λ$ -Choosable图中的最小顶点数。本文确定所有$λ$的$ ϕ（λ）$的值。
For a multi-set $λ=\{k_1,k_2, \ldots, k_q\}$ of positive integers, let $k_λ = \sum_{i=1}^q k_i$. A $λ$-list assignment of $G$ is a list assignment $L$ of $G$ such that the colour set $\bigcup_{v \in V(G)}L(v)$ can be partitioned into the disjoint union $C_1 \cup C_2 \cup \ldots \cup C_q$ of $q$ sets so that for each $i$ and each vertex $v$ of $G$, $|L(v) \cap C_i| \ge k_i$. We say $G$ is $λ$-choosable if $G$ is $L$-colourable for any $λ$-list assignment $L$ of $G$. The concept of $λ$-choosability puts $k$-colourability and $k$-choosability in the same framework: If $λ= \{k\}$, then $λ$-choosability is equivalent to $k$-choosability; if $λ$ consists of $k $ copies of $1$, then $λ$-choosability is equivalent to $k $-colourability. If $G$ is $λ$-choosable, then $G$ is $k_λ$-colourable. On the other hand, there are $k_λ$-colourable graphs that are not $λ$-choosable, provided that $λ$ contains an integer larger than $1$. Let $ϕ(λ)$ be the minimum number of vertices in a $k_λ$-colourable non-$λ$-choosable graph. This paper determines the value of $ϕ(λ)$ for all $λ$.
