Choosability with limited number of colors.
Marc Demange, D. de Werra · arXiv (Cornell University) · 2016
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 list. We study complexity issues of choosability of graphs when the number $k$ of colors is limited. We get results which differ surprisingly from the usual case where $k$ is implicit and which extend known results for the usual case. We also exhibit some classes of graphs (defined by structural properties of their blocks) which are choosable. Finally we show that for any $\ell\geq 3$ and any $k\geq 2\ell-2$ there is a bipartite graph which is $\ell$-choosable with $k$ colors but not with $k+1$.