Back to Search
Start Over
Bad list assignments for non‐k $k$‐choosable k $k$‐chromatic graphs with 2k+2 $2k+2$‐vertices.
- 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]
- Subjects :
- *LOGICAL prediction
*COMPLETE graphs
*BIPARTITE graphs
Subjects
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