A 4-choosable graph that is not (8:2)-choosable

List coloring is a generalization of graph coloring introduced by Erdős, Rubin and Taylor in 1980, which has become extensively studied in graph theory. A graph $G$ is said to be $k$-choosable, or $k$-list-colorable, if, for every way of assigning a list (set) of $k$ colors to each vertex of $G$, it is possible to choose a color from each list in such a way that no two neighboring vertices receive the same color. Note that if the lists are all the same, then this is asking for $G$ to have chromatic number at most $k$.

One might think that the case where all the lists are the same would be the hardest: surely making the lists different should make it easier to ensure that neighboring vertices have different colors. Rather surprisingly, however, this is not the case. A counterexample is provided by the complete bipartite graph $K_{2,4}$. If the two vertices in the first vertex class are assigned the lists $\{a,b\}$ and $\{c,d\}$, while the vertices in the other vertex class are assigned the lists $\{a,c\}$, $\{a,d\}$, $\{b,c\}$ and $\{b,d\}$, then it is easy to check that it is not possible to obtain a proper coloring from these lists, so $G$ is not 2-choosable, and yet the chromatic number of $G$ is 2. A famous theorem of Galvin, which solved the so-called Dinitz conjecture, states that the line graph of the complete bipartite graph $K_{n,n}$ is $n$-choosable. Equivalently, if each square of an $n\times n$ grid is assigned a list of $n$ colors, it is possible to choose a color from each list in such a way that no color appears more than once in any row or column.

One can generalize this notion by requiring a choice of not just one color from each list, but some larger number of colors. A graph $G$ is said to be $(A,B)$-list-colorable if, for every assignment of lists to the vertices of $G$, each consisting of $A$ colors, there is an assignment of sets of $B$ colors to the vertices such that each vertex is assigned a set that is a subset of its list and the sets assigned to pairs of adjacent vertices are disjoint. (When $B=1$ this simply says that $G$ is $A$-choosable.) In this short paper, the authors answer a question that has remained open for almost four decades since it was posed by Erdős, Rubin and Taylor in their seminal paper: if a graph is $(A,B)$-list-colorable, is it true that it is also $(mA,mB)$-list-colorable for every $m\ge 1$? Quite surprisingly, the answer is again negative - the authors construct a graph that is $(4,1)$-list-colorable but not $(8,2)$-list-colorable.