Complexity of list coloring $K_n$ with $n$ colors

Question

The list coloring problem is, given a set $L(v)$ colors for each vertex $v \in G$, is there a proper vertex coloring, $c$, of $G$, such that $c(v) \in L(v), \forall v$.

I was wondering, for complete graphs $K_n$, is list coloring NP-complete? Does this change if $\bigcup_{v \in K_n} L(v) = \{1,2\dots n\}$?

Answer 1

Consider list coloring the complete graph, where the available colors for vertex $v$ are $L(v)$.

Form a bipartite graph in which the left-hand side corresponds to vertices and the right-hand side corresponds to colors. Connect $v$ on the left-hand side to all colors in $L(v)$ in the right-hand side.

There is a list coloring iff there is a matching saturating the left-hand side. You can decide whether this is the case by running an algorithm for bipartite perfect matching.

Answer 2

To complement Yuval's answer, the problem is solvable in polynomial-time more generally for block graphs which generalize complete graphs and trees. See the algorithm of Jansen [1].

On the other hand, the problem (as you probably know) remains NPC for many graphs that are close to being complete in some sense. This includes complete bipartite graphs, complete graphs minus a matching and complete split graphs (see [2, Table 1] for an overview).

---

[1] Jansen, Klaus. "Complexity results for the optimum cost chromatic partition problem." Universit¨at Trier, Mathematik/Informatik, Forschungsbericht 96–41 (1996).

[2] Bonomo, Flavia, Guillermo Durán, and Javier Marenco. "Exploring the complexity boundary between coloring and list-coloring." Annals of Operations Research 169.1 (2009): 3.