Counterexamples to Relaxed Multiplication in List Coloring
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 answer this question negatively by constructing a graph with chromatic number and choice number $k$ that is not $(km+1:m)$-choosable for every $k\ge3$ and $m\ge10$. More generally, for integers $k\ge3$, $m\ge2$, and $t\ge0$, satisfying $m>8t+ε$, where $ε\in\{0,1\}$ is the parity of $m$, we construct such a graph that is not $(km+t:m)$-choosable. This also answers negatively the equivalent question of Xu and Zhu [SIAM J. Discrete…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2611.03151
curl -X POST /api/v1/records/arxiv/2611.03151/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2611.03151/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'