Complexity of choosability with a small palette of colors

Marc Demange, Dominique de Werra

A graph is $\ell$-choosable if, for any choice of lists of $\ell$ colors for each vertex, there is a list coloring, which is a coloring where each vertex receives a color from its…