




















Let $φ(k)$ be the minimum number of vertices in a non-$k$-choosable $k$-chromatic graph. The Ohba conjecture, confirmed by Noel, Reed and Wu, asserts that $φ(k) \ge 2k+2$. This bound is tight if $k$ is even. If $k$ is odd, then it is known that $φ(k) \le 2k+3$ and it is conjectured by Noel that $φ(k) = 2k+3$. 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 $k_λ$-list assignment $L$ for which the colour set $\cup_{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$. Let $φ(λ)$ be the minimum number of vertices in a non-$λ$-choosable $k_λ$-chromatic graph. Let $1_λ$ be the multiplicity of $1$ in $λ$, and let $o_λ$ be the number of elements in $λ$ that are odd integers. We prove that if $1_λ \ne k_λ$, then $2k_λ+1_λ+2 \leqslant φ(λ) \leqslant 2k_λ+ o_λ+2$. In particular, if $1_λ=o_λ=t$, i.e. $λ$ contains no odd integer greater than $1$, then $φ(λ) = 2k_λ+t+2$. We also prove that $φ(λ) \leqslant 2k_λ+5 1_λ+3$. In particular, if $1_λ=0$, then $2k_λ+2 \leqslant φ(λ) \leqslant 2k_λ+3$.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。