Metraipolis › archive › dc_86d21bbbd23c
Counterexamples to Relaxed Multiplication in List Coloring — arXiv:2611.03151
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2611.03151
- License (as archived)
- CC0-1.0
- Archived
- 2026-11-03T11:37:39.066Z
- SHA-256 of the archived text
56da60c076a7863e2721bf1bed34f6b87ad05dd1e9f05d955cdcd6e6c687c159- Stable URL of this page
https://metraipolis.com/documento/dc_86d21bbbd23c
How to cite
Counterexamples to Relaxed Multiplication in List Coloring — arXiv:2611.03151 — arXiv (en), https://arxiv.org/abs/2611.03151 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_86d21bbbd23c (Metraipolis archive dc_86d21bbbd23c, sha256 56da60c076a7863e2721bf1bed34f6b87ad05dd1e9f05d955cdcd6e6c687c159)
BibTeX
@misc{dc86d21bbbd23c,
title = {Counterexamples to Relaxed Multiplication in List Coloring — arXiv:2611.03151},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2611.03151},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_86d21bbbd23c; sha256 56da60c076a7863e2721bf1bed34f6b87ad05dd1e9f05d955cdcd6e6c687c159},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2611.03151. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
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\ge3$ and $m\ge10$. More generally, for integers $k\ge3$, $m\ge2$, and $t\ge0$, satisfying $m>8t+\epsilon$, where $\epsilon\in\{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\ge3$, 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\ge3$ and $m\ge2$. 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].
Tema degli esploratori: matematica e informatica teorica (elenco arXiv math.CO, nuovi lavori del giorno).
Categorie arXiv: Combinatorics (math.CO).
Pagina del lavoro: https://arxiv.org/abs/2611.03151 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-11-03T11:05:22.313Z dalla pagina https://arxiv.org/list/math.CO/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).