The strong fractional choice number can exceed the choice number
Abstract
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 chfs(G)≤ch(G) for every graph G. Here ch(G) is the choice number of a graph G, and chfs(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≥ r. In this paper, we prove that, for all integers t≥0 and b≥7t+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 chfs(G)−ch(G) over graphs of choice number three is at least 1/7. We further prove that, for all integers k≥4, t≥0 and b≥3t+2, there is a graph G with ch(G)=k that is not (kb+t,b)-choosable. For every k≥4, this establishes the stronger lower bound 1/3 on the supremum of chfs(G)−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 W5.
Related
- The Choice Number of Random Graphs
- Nonparametric hazard rate estimation with associated kernels and minimax bandwidth choice
- Simulated Annealing for Model‐Robust Partial Profile Choice Designs in Healthcare Preference Studies
- Why Customer Choice Models Matter
- Existence of bases implies the axiom of choice, a foundation-free proof
BibTeX
@misc{gu2026strong,
title = {{The strong fractional choice number can exceed the choice number}},
author = {Yangyan Gu and Rongxing Xu},
howpublished = {arXiv},
year = {2026},
month = nov,
doi = {10.48550/arxiv.2611.03236},
eprint = {2611.03236},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2611.03236},
}
RIS
TY - UNPB
TI - The strong fractional choice number can exceed the choice number
AU - Yangyan Gu
AU - Rongxing Xu
PY - 2026
DA - 2026/11/02
PB - arXiv
DO - 10.48550/arxiv.2611.03236
UR - https://arxiv.org/abs/2611.03236
AB - 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 ch_f^s(G)≤ch(G) for every graph G. Here ch(G) is the choice number of a graph G, and 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≥ r. In this paper, we prove that, for all integers t≥0 and b≥7t+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 ch_f^s(G)−ch(G) over graphs of choice number three is at least 1/7. We further prove that, for all integers k≥4, t≥0 and b≥3t+2, there is a graph G with ch(G)=k that is not (kb+t,b)-choosable. For every k≥4, this establishes the stronger lower bound 1/3 on the supremum of ch_f^s(G)−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.
ER -