Complexity of list coloring problems with a fixed total number of colors (Q1348378)

In the list coloring problem, a graph \(G=(V,E)\) is given and with each vertex \(v\), a list of colors \(L(v)\). The problem is to select for each vertex a color from its list such that adjacent vertices get different colors. This paper looks at versions of the problem where additionally there is a function \(p\), such that each color \(j\) is given to exactly (or respectively at most) \(p(j)\) vertices. The paper establishes NP-completeness for the problem when there are three colors for bipartite planar graphs, and shows it is polynomially time solvable when there are two colors. The paper also shows that for a fixed number of colors, the problems (and the standard list coloring problem) are polynomially solvable for treeds and for graphs of bounded treewidth. Treeds can be defined as follows. A forest is a treed. If we have a treed and replace one vertex \(v\) by a treed such that each vertex in the latter treed is exactly adjacent to all neighbors of \(v\), then we again have a treed.