Minimum non-chromatic-choosable graphs with given chromatic number

Abstract

A graph $G$ is called chromatic-choosable if $\ddot{I}‡(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)|=2k+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)|=2k+2$ are $k$-choosable. In particular, if $\ddot{I}‡(G)$ is odd and $|V(G)|\le 2\ddot{I}‡(G)+2$, then $G$ is chromatic-choosable, which was conjectured by Noel.

33 pages