Complexity of choosability with a small palette of colors

arXiv1601.01768MaRDI QIDQ6269087

Dominique De Werra, Marc Demange

Publication date: 7 January 2016

Abstract: 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.

This page was built for publication: Complexity of choosability with a small palette of colors

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6269087)