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

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\}$$?

• Your title doesn't match your question. What does "with $n$ colors" mean in the title? Dec 28, 2019 at 21:13
• It references the second question, where we have the union of all colors have order $n$. Dec 28, 2019 at 21:14

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.