Counterexamples to Relaxed Multiplication in List Coloring
Abstract
Jiang and Zhu [J. Combin. Theory Ser. B, 137 (2019) 112--117] asked whether every k-choosable graph is (km+1:m)-choosable for every positive integer m. We answer this question negatively by constructing a graph with chromatic number and choice number k that is not (km+1:m)-choosable for every k≥3 and m≥10. More generally, for integers k≥3, m≥2, and t≥0, satisfying m>8t+ε, where ε∈{0,1} is the parity of m, we construct such a graph that is not (km+t:m)-choosable. This also answers negatively the equivalent question of Xu and Zhu [SIAM J. Discrete Math., 36 (2022) 2585--2601] asking whether the strong fractional choice number of every graph is at most its choice number. This also indicates that, for each k≥3, the supremum of the strong fractional choice numbers of graphs with choice number k is at least k+1/8. When t=0, our construction yields counterexamples to multiplication for every k≥3 and m≥2. In particular, it yields a $3$-choosable graph on $91$ vertices that is not (6:2)-choosable, answering a question of Dvořák, Hu and Sereni [ Adv. Comb. (2019), Paper No. 5].
Related
- List 3-Coloring in tame classes of graphs in quasipolynomial time
- List coloring C3-free planar graphs with a sparse matching of restricted lists
- Sufficiency of Hall's Condition for Graphic List Coloring
- The List Edge-Coloring Conjecture for New Infinite Families
- Restricting Odd Antiholes in Critical Graphs via List Coloring
BibTeX
@misc{hu2026counterexamples,
title = {{Counterexamples to Relaxed Multiplication in List Coloring}},
author = {Xiaolan Hu and Jiao Li},
howpublished = {arXiv},
year = {2026},
month = nov,
doi = {10.48550/arxiv.2611.03151},
eprint = {2611.03151},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2611.03151},
}
RIS
TY - UNPB
TI - Counterexamples to Relaxed Multiplication in List Coloring
AU - Xiaolan Hu
AU - Jiao Li
PY - 2026
DA - 2026/11/02
PB - arXiv
DO - 10.48550/arxiv.2611.03151
UR - https://arxiv.org/abs/2611.03151
AB - Jiang and Zhu [J. Combin. Theory Ser. B, 137 (2019) 112--117] asked whether every k-choosable graph is (km+1:m)-choosable for every positive integer m. We answer this question negatively by constructing a graph with chromatic number and choice number k that is not (km+1:m)-choosable for every k≥3 and m≥10. More generally, for integers k≥3, m≥2, and t≥0, satisfying m>8t+ε, where ε∈{0,1} is the parity of m, we construct such a graph that is not (km+t:m)-choosable. This also answers negatively the equivalent question of Xu and Zhu [SIAM J. Discrete Math., 36 (2022) 2585--2601] asking whether the strong fractional choice number of every graph is at most its choice number. This also indicates that, for each k≥3, the supremum of the strong fractional choice numbers of graphs with choice number k is at least k+1/8. When t=0, our construction yields counterexamples to multiplication for every k≥3 and m≥2. In particular, it yields a $3$-choosable graph on $91$ vertices that is not (6:2)-choosable, answering a question of Dvořák, Hu and Sereni [ Adv. Comb. (2019), Paper No. 5].
ER -