Bad list assignments for non--choosable -chromatic graphs with -vertices
Abstract
It was conjectured by Ohba, and proved by Noel, Reed and Wu that -chromatic graphs with are chromatic-choosable. This upper bound on is tight: if is even, then and are -chromatic graphs with vertices that are not chromatic-choosable. It was proved by Zhu and Zhu that these are the only non--choosable complete -partite graphs with vertices. For , a bad list assignment of is a -list assignment of such that is not -colourable. Bad list assignments for 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 . Using these results, we characterize all non--choosable -chromatic graphs with vertices.
CONFLICT OF INTEREST STATEMENT
The authors declare no conflict of interest.