On (4,2)-Choosable Graphs

Abstract

A graph $G$ is called $(a,b)$-choosable if for any list assignment $L$ which assigns to each vertex $v$ a set $L(v)$ of $a$ permissible colours, there is a $b$-tuple $L$-colouring of $G$. An $(a,1)$-choosable graph is also called $a$-choosable. In the pioneering paper on list colouring of graphs by Erdős, Rubin and Taylor, $2$-choosable graphs are characterized. Confirming a special case of a conjecture of Erdős--Rubin--Taylor, Tuza and Voigt proved that $2$-choosable graphs are $(2m,m)$-choosable for any positive integer $m$. On the other hand, Voigt proved that if $m$ is an odd integer, then these are the only $(2m,m)$-choosable graphs; however, when $m$ is even, there are $(2m,m)$-choosable graphs that are not $2$-choosable. A graph is called $3$-choosable-critical if it is not $2$-choosable, but all its proper subgraphs are $2$-choosable. Voigt conjectured that for every positive integer $m$, all bipartite $3$-choosable-critical graphs are $(4m,2m)$-choosable. In this paper, we determine which $3$-choosable-critical graphs are $(4,2)$-choosable, refuting Voigt's conjecture in the process. Nevertheless, a weaker version of the conjecture is true: we prove that there is an even integer $k$ such that for any positive integer $m$, every bipartite $3$-choosable-critical graph is $(2km,km)$-choosable. Moving beyond $3$-choosable-critical graphs, we present an infinite family of non-$3$-choosable-critical graphs which have been shown by computer analysis to be $(4,2)$-choosable. This shows that the family of all $(4,2)$-choosable graphs has rich structure.

18 pages, 8 figures. Now includes source code in ancillary files