Paperlane

no. 13 · Wednesday 11 November 2026

The strong fractional choice number can exceed the choice number by an arbitrarily large amount

Yangyan Gu and Rongxing Xu

math.CO · v3 · 18 pp

Abstract

Erdős, Rubin and Taylor asked whether $(a,b)$-choosability implies $(am,bm)$-choosability for all positive integers $a,b,m$. Dvořák, Hu and Sereni disproved this for $(a,b,m)=(4,1,2)$ and asked whether a $3$-choosable graph can fail to be $(6,2)$-choosable. Following an earlier discussion by Jiang and Zhu, Li and Zhu asked whether every $k$-choosable graph is $(kb+1,b)$-choosable. Equivalently, Xu and Zhu asked whether $\mathrm{ch}_f^s(G)\le\mathrm{ch}(G)$ for every graph $G$, where $\mathrm{ch}(G)$ is its choice number and $\mathrm{ch}_f^s(G)$ is its strong fractional choice number, 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 of choice number three that is not $(3b+t,b)$-choosable. This answers the question of Dvořák, Hu and Sereni affirmatively and the other questions negatively, even for planar graphs. Next, for all integers $k\ge4$, $t\ge0$ and $b\ge3t+2$, we construct a graph of choice number $k$ that is not $(kb+t,b)$-choosable, using only the six-vertex wheel $W_5$ as its core gadget. The case $t=0$ and $b=2$ recovers the result of Dvořák, Hu and Sereni. The supremum of $\mathrm{ch}_f^s(G)-\mathrm{ch}(G)$ is at least $1/7$ over planar graphs of choice number three, and at least $1/3$ over graphs of choice number $k$ for each $k\ge4$. Finally, for every sufficiently large integer $k$, we construct a graph $G$ with $\mathrm{ch}(G)=k$ that is not $(2k+t,2)$-choosable, where $t\ge C\sqrt{k}$ for an absolute constant $C>0$. Thus the gap is unbounded even with multiplicity fixed at two. We further obtain $k+Ω(\sqrt{k})\le\sup\{\mathrm{ch}_f^s(G):\mathrm{ch}(G)=k\}\le2^{(1+o(1))k}$ as $k$ tends to infinity.

comments
18 pages, 3 figures
fields
Combinatorics
pdf ↗ page arXiv:2611.03236 ↗