Paperlane

no. 12 · Tuesday 10 November 2026

Counterexamples to Relaxed Multiplication in List Coloring

Xiaolan Hu and Jiao Li

math.CO · v2

Abstract

Jiang and Zhu [J. Combin. Theory Ser. B 137 (2019) 112–117] asked whether every $k$-choosable graph is $(km+1:m)$-choosable for every positive integer $m$. We show that, for all integers $k\ge3$, $m\ge2$, and $t\ge0$ satisfying $m>8t+ε$, where $ε\in\{0,1\}$ and $m\equivε\pmod2$, there is a graph with chromatic number and choice number both equal to $k$ that is not $(km+t:m)$-choosable. This answers their question negatively for every $k\ge3$ and $m\ge10$. In particular, our construction yields a $3$-choosable graph on $91$ vertices that is not $(6:2)$-choosable, answering a question of Dvořák, Hu and Sereni [Adv. Comb. (2019), Paper No.~5]. More generally, for every fixed $b\ge1$, $m\ge2$, and $t\ge0$, we construct an $(a:b)$-choosable graph that is not $(am+t:bm)$-choosable for all sufficiently large $a$, with an explicit bound on $a$. Let $F(a,b)$ be the supremum of the strong fractional choice numbers of $(a:b)$-choosable graphs. We prove that for every fixed $b\ge1$, $F(a,b)-\frac ab$ tends to infinity as $a\to\infty$.

fields
Combinatorics
pdf ↗ page arXiv:2611.03151 ↗