The strong fractional choice number can exceed the choice number

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$.

Authors

Publication Details

Journal
arXiv (Cornell University)
Published
2026-11-02
DOI
https://doi.org/10.48550/arxiv.2611.03236
Primary Topic
Advanced Graph Theory Research
Type
preprint
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
preprint

The strong fractional choice number can exceed the choice number

Yangyan Gu, Rongxing Xu
arXiv (Cornell University)
Advanced Graph Theory Research
preprint

The strong fractional choice number can exceed the choice number

Yangyan Gu, Rongxing Xu
preprint en

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 $\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$.

arXiv (Cornell University)
Advanced Graph Theory Research
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Laika access coming soon