Complessità della lista Colorazione $ k_n $ con $ n $ colori

Question

Elenco Problema da colorare è, dato un set $ L (V) $ colori per ogni vertice $ v \ in G $ , c'è una colorazione vertice appropriata, $ c $ , di $ G $ , in modo tale da $ c (v) \ inL (V), \ forall V $ .

Mi stavo chiedendo, per i grafici completi $ k_n $ , è la lista Coloring NP-Completa?Questo cambia se $ \ bigcup_ {v \ in k_n} l (v)={1,2 \ dots n \} $ ?

Answer 1

Elenco Considera Colorare il grafico completo, in cui i colori disponibili per Vertex $ V $ sono $ l (v) $.

Formare un grafico bipartite in cui il lato sinistro corrisponde ai vertici e il lato destro corrisponde ai colori.Connetti $ V $ sul lato sinistro a tutti i colori in $ l (v) $ nellato destro.

C'è un elenco Colorare IFF Se è un gabinetto saturare il lato sinistro.Puoi decidere se questo è il caso eseguendo un algoritmo per la corrispondenza perfetta bipartite.

Answer 2

Per completare la risposta di Yuval, il problema è solvibile in tempo polinomiale in generale per i grafici a blocchi che generalizzano grafici e alberi completi.Vedi l'algoritmo di Jansen [1].

D'altra parte, il problema (come probabilmente sapete) rimane NPC per molti grafici che sono vicini a essere completi in un certo senso.Ciò include grafici bipartite completi, i grafici completi meno un grafico diviso e diviso di corrispondenza (vedere [2, Tabella 1] per una panoramica).

---

.

[1] Jansen, Klaus."Risultati della complessità per il problema di partizione cromatica dei costi ottimale."Universit a Treviri, Mathematik / Informatik, Forschungsbericht 96-41 (1996).

[2] Bonoma, Flavia, Guillermo Durán e Javier Marenco."Esplorando il confine di complessità tra colorazione e listino."Annals of Operations Research 169.1 (2009): 3.