HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

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

Submitted by: @import:stackexchange-cs··
0
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\}$?

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.

Context

StackExchange Computer Science Q#118984, answer score: 3

Revisions (0)

No revisions yet.