4
$\begingroup$

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

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

2 Answers 2

3
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.