Minimum non-chromatic-choosable graphs with given chromatic number

Abstract A graph G is called chromatic-choosable if $\chi (G)=ch(G)$ . A natural problem is to determine the minimum number of vertices in a non-chromatic-choosable graph with given chromatic number. It was conjectured by Ohba, and proved by Noel, Reed, and Wu that k -chromatic graphs G with $|V(G)| \le 2k+1$ are chromatic-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 non-chromatic-choosable k -chromatic graphs with $|V(G)| =2 k+2$ . Some subgraphs of these two graphs are also non-chromatic-choosable. The main result of this paper is that all other k -chromatic graphs G with $|V(G)| =2 k+2$ are chromatic-choosable. In particular, if $\chi (G)$ is odd and $|V(G)| \le 2\chi (G)+2$ , then G is chromatic-choosable, which was conjectured by Noel.