论文标题
具有给定色数的最小非颜色选择图
Minimum non-chromatic-choosable graphs with given chromatic number
论文作者
论文摘要
如果$χ（g）= CH（g）$，则图$ G $称为色度可选。一个自然的问题是确定$ K $ -CHROMATIC非$ K $ -Choosable图中的最小顶点。它由OHBA猜想，并由Noel，Reed和Wu证明，$ k $ -Chronic Graphs $ G $ with $ | v（g）| \ le 2k+1 $是$ K $ -Choosable。 $ | v（g）| $的上限很紧。众所周知，如果$ k $均匀，那么$ g = k_ {3 \ star（k/2+1），1 \ star（k/2-1）} $和$ g = k_ {4，2 \ star（k-1）$是$ k $ -Chromation图，带有$ | v（g）| = 2 k+2 $不是$ k $ -Choosable。这两个图的某些子图也非$ k $ - 可选。本文的主要结果是所有其他$ k $ -Chromation Graphs $ g $ with $ | v（g）| = 2 k+2 $是$ k $ -Choosable。特别是，如果$χ（g）$是奇数，$ | v（g）| \ le2χ（g）+2 $，然后$ g $是彩色选择的，由Noel猜想。
A graph $G$ is called chromatic-choosable if $χ(G)=ch(G)$. A natural problem is to determine the minimum number of vertices in a $k$-chromatic non-$k$-choosable graph. It was conjectured by Ohba, and proved by Noel, Reed and Wu that $k$-chromatic graphs $G$ with $|V(G)| \le 2k+1$ are $k$-choosable. This upper bound on $|V(G)|$ is tight. It is known that if $k$ is even, then $G=K_{3 \star (k/2+1), 1 \star (k/2-1)}$ and $G=K_{4, 2 \star (k-1)}$ are $k$-chromatic graphs with $|V(G)| =2 k+2$ that are not $k$-choosable. Some subgraphs of these two graphs are also non-$k$-choosable. The main result of this paper is that all other $k$-chromatic graphs $G$ with $|V(G)| =2 k+2$ are $k$-choosable. In particular, if $χ(G)$ is odd and $|V(G)| \le 2χ(G)+2$, then $G$ is chromatic-choosable, which was conjectured by Noel.
