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 Jiang and Zhu, 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, and $\operatorname{ch}_f^s(G)$ is the strong fractional choice number, defined as the infimum of real $r$ such that $G$ is $(a,b)$-choosable for all positive integers $a,b$ with $a/b\ge r$. We prove that, for all integers $t\ge0$ and $b\ge7t+2$, there is a planar graph $G$ with $\operatorname{ch}(G)=3$ that is not $(3b+t,b)$-choosable. This answers all these questions and gives a lower bound of $1/7$ on the supremum of $\operatorname{ch}_f^s(G)-\operatorname{ch}(G)$ over planar graphs of choice number three. For all integers $k\ge4$, $t\ge0$ and $b\ge3t+2$, we construct a graph $G$ with $\operatorname{ch}(G)=k$ that is not $(kb+t,b)$-choosable, using the six-vertex wheel $W_5$ as its core gadget. This gives the corresponding lower bound $1/3$ for each $k\ge4$. The case $t=0$ and $b=2$ recovers the main result of Dvořák, Hu and Sereni. Finally, for every integer $t\ge1$, there are a positive integer $k$ and a $k$-choosable graph that is not $(8k+4t-1,8)$-choosable. Thus the difference between the strong fractional choice number and the choice number is unbounded, even with multiplicity fixed at eight. We further prove $k+Ω(\log k)\le\sup\{\operatorname{ch}_f^s(G):\operatorname{ch}(G)=k\}\le2^{(1+o(1))k}$ as $k$ tends to infinity.
- comments
- 16 pages, 3 figures
- fields
- Combinatorics