Metraipolis › archive › dc_710100617fb1
The strong fractional choice number can exceed the choice number — arXiv:2611.03236
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2611.03236
- License (as archived)
- CC0-1.0
- Archived
- 2026-11-03T11:37:40.495Z
- SHA-256 of the archived text
464c3a3d68a2421131e267a53040dc743d0e1c8fa2e852caf3bf969315c71739- Stable URL of this page
https://metraipolis.com/documento/dc_710100617fb1
How to cite
The strong fractional choice number can exceed the choice number — arXiv:2611.03236 — arXiv (en), https://arxiv.org/abs/2611.03236 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_710100617fb1 (Metraipolis archive dc_710100617fb1, sha256 464c3a3d68a2421131e267a53040dc743d0e1c8fa2e852caf3bf969315c71739)
BibTeX
@misc{dc710100617fb1,
title = {The strong fractional choice number can exceed the choice number — arXiv:2611.03236},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2611.03236},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_710100617fb1; sha256 464c3a3d68a2421131e267a53040dc743d0e1c8fa2e852caf3bf969315c71739},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2611.03236. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
Erdős, Rubin and Taylor asked whether every $(a,b)$-choosable graph is $(am,bm)$-choosable for all positive integers $a,b,m$. Dvořák, Hu and Sereni disproved this by constructing a $4$-choosable graph that is not $(8,2)$-choosable, and asked whether a $3$-choosable graph can fail to be $(6,2)$-choosable. As a weakening, Li and Zhu asked whether every $k$-choosable graph is $(kb+1,b)$-choosable for all positive integers $k,b$. Equivalently, Xu and Zhu asked whether $\operatorname{ch}_f^s(G)\le\operatorname{ch}(G)$ for every graph $G$. Here $\operatorname{ch}(G)$ is the choice number of a graph $G$, and $\operatorname{ch}_f^s(G)$ is the strong fractional choice number of $G$, which is defined as the infimum of the real numbers $r$ such that $G$ is $(a,b)$-choosable for all positive integers $a,b$ with $a/b\ge r$. In this paper, we prove that, for all integers $t\ge0$ and $b\ge7t+2$, there is a planar graph $G$ with choice number three that is not $(3b+t,b)$-choosable. For $(b,t)=(2,0)$, our construction gives an affirmative answer to the question of Dvořák, Hu and Sereni. This family answers the questions of Li and Zhu and of Xu and Zhu negatively, and shows that the supremum of $\operatorname{ch}_f^s(G)-\operatorname{ch}(G)$ over graphs of choice number three is at least $1/7$. We further prove that, for all integers $k\ge4$, $t\ge0$ and $b\ge3t+2$, there is a graph $G$ with $\operatorname{ch}(G)=k$ that is not $(kb+t,b)$-choosable. For every $k\ge4$, this establishes the stronger lower bound $1/3$ on the supremum of $\operatorname{ch}_f^s(G)-\operatorname{ch}(G)$. The latter construction also produces simpler versions of the counterexamples of Dvořák, Hu and Sereni. It is worth mentioning that the core gadgets in both constructions are very simple. The former is an eight-vertex graph, and the latter is the six-vertex wheel $W_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.03236 — 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.316Z dalla pagina https://arxiv.org/list/math.CO/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).