Back to Search Start Over

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

Authors :
Zhu, Jialu
Zhu, Xuding
Source :
Journal of Graph Theory. Dec2023, Vol. 104 Issue 4, p712-726. 15p.
Publication Year :
2023

Abstract

It was conjectured by Ohba, and proved by Noel, Reed and Wu that k $k$‐chromatic graphs G $G$ with ∣V(G)∣≤2k+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 K3⋆(k∕2+1),1⋆(k∕2−1) ${K}_{3\star (k\unicode{x02215}2+1),1\star (k\unicode{x02215}2-1)}$ and K4,2⋆(k−1) ${K}_{4,2\star (k-1)}$ are k $k$‐chromatic graphs with 2k+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 2k+2 $2k+2$ vertices. For G∈{K3⋆(k∕2+1),1⋆(k∕2−1),K4,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=K4,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=K3⋆(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 2k+2 $2k+2$ vertices. [ABSTRACT FROM AUTHOR]

Details

Language :
English
ISSN :
03649024
Volume :
104
Issue :
4
Database :
Academic Search Index
Journal :
Journal of Graph Theory
Publication Type :
Academic Journal
Accession number :
173013979
Full Text :
https://doi.org/10.1002/jgt.22998