patternMinor
Complexity of list coloring $K_n$ with $n$ colors
Viewed 0 times
coloringwithcolorsk_nlistcomplexity
Problem
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\}$?
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\}$?
Solution
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.
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.
Context
StackExchange Computer Science Q#118984, answer score: 3
Revisions (0)
No revisions yet.