Abstract
It was conjectured by Ohba, and proved by Noel, Reed and Wu that k-chromatic graphs G with.V (G). = 2k + 1 are chromatic-choosable. This upper bound on.V (G). is tight: if k is even, then K-3*( k/ 2+ 1),K- 1.(k/2-1) and K-4,K-2*( k- 1) are k-chromatic graphs with 2k + 2 vertices that are not chromaticchoosable.
It was proved by Zhu and Zhu that these are the only non-k-choosable complete k-partite graphs with 2k + 2 vertices. For G. {K-3*( k/2+1),K-1*(k/2- 1), K-4,K-2*( k- 1)}, a bad list assignment of G is a k-list assignment L of G such that G is not L-colourable.
Bad list assignments for G = K-4,K-2*( k- 1) were characterized by Enomoto, Ohba, Ota and Sakamoto. In this paper, we first give a simpler proof of this result, and then we characterize bad list assignments for G = K3.( k/ 2+ 1), 1.(k/2-1).
Using these results, we characterize all non-k-choosable k-chromatic graphs with 2k + 2 vertices.