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.