Problem Statement
A graph is $(a,b)$-choosable if for any assignment of a list of $a$ colours to each of its vertices there is a subset of $b$ colours from each list such that the subsets of adjacent vertices are disjoint.
If $G$ is $(a,b)$-choosable then $G$ is $(am,bm)$-choosable for every integer $m\geq 1$.
If $G$ is $(a,b)$-choosable then $G$ is $(am,bm)$-choosable for every integer $m\geq 1$.
Categories:
Graph Theory Chromatic Number
Progress
A problem of Erdős, Rubin, and Taylor [ERT80]. Note that $G$ is $(a,1)$-choosable corresponds to being $a$-choosable, that is, the list chromatic number satisfies $\chi_L(G)\leq a$.This is false: Dvořák, Hu, and Sereni [DHS19] construct a graph which is $(4,1)$-choosable but not $(8,2)$-choosable.
See also the entry in the graphs problem collection.
Source: erdosproblems.com/632 | Last verified: January 15, 2026