Complexity of list coloring problems with a fixed total number of colors Original Research Article

We study list coloring problems where the total number k of colors on all lists is fixed. Such problems are known to be NP-Complete even for planar bipartite graphs and k=3. We give polynomial algorithms for some special cases of these problems.