Volume 104, Issue 4 pp. 712-726
ARTICLE

Bad list assignments for non- k $k$ -choosable k $k$ -chromatic graphs with 2 k + 2 $2k+2$ -vertices

Jialu Zhu

Jialu Zhu

School of Mathematical Sciences, Zhejiang Normal University, Jinhua, Zhejiang Province, China

Search for more papers by this author
Xuding Zhu

Corresponding Author

Xuding Zhu

School of Mathematical Sciences, Zhejiang Normal University, Jinhua, Zhejiang Province, China

Correspondence Xuding Zhu, School of Mathematical Sciences, Zhejiang Normal University, 688 Yingbin Road, Jinhua, Zhejiang Province, 321004, China.

Email: [email protected]

Search for more papers by this author
First published: 15 June 2023
Citations: 1

Abstract

It was conjectured by Ohba, and proved by Noel, Reed and Wu that k $k$ -chromatic graphs G $G$ with V ( G ) 2 k + 1 $| V(G)| \le 2k+1$ are chromatic-choosable. This upper bound on V ( G ) $| V(G)| $ is tight: if k $k$ is even, then K 3 ( k 2 + 1 ) , 1 ( k 2 1 ) ${K}_{3\star (k\unicode{x02215}2+1),1\star (k\unicode{x02215}2-1)}$ and K 4 , 2 ( k 1 ) ${K}_{4,2\star (k-1)}$ are k $k$ -chromatic graphs with 2 k + 2 $2k+2$ vertices that are not chromatic-choosable. It was proved by Zhu and Zhu that these are the only non- k $k$ -choosable complete k $k$ -partite graphs with 2 k + 2 $2k+2$ vertices. For G { K 3 ( k 2 + 1 ) , 1 ( k 2 1 ) , K 4 , 2 ( k 1 ) } $G\in \{{K}_{3\star (k\unicode{x02215}2+1),1\star (k\unicode{x02215}2-1)},{K}_{4,2\star (k-1)}\}$ , a bad list assignment of G $G$ is a k $k$ -list assignment L $L$ of G $G$ such that G $G$ is not L $L$ -colourable. Bad list assignments for G = K 4 , 2 ( k 1 ) $G={K}_{4,2\star (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 = K 3 ( k 2 + 1 ) , 1 ( k 2 1 ) $G={K}_{3\star (k\unicode{x02215}2+1),1\star (k\unicode{x02215}2-1)}$ . Using these results, we characterize all non- k $k$ -choosable k $k$ -chromatic graphs with 2 k + 2 $2k+2$ vertices.

CONFLICT OF INTEREST STATEMENT

The authors declare no conflict of interest.

The full text of this article hosted at iucr.org is unavailable due to technical difficulties.