Complexité de la liste Coloriage $ K_N $ avec des couleurs $ N $

Question

the Problème de coloration de liste est, étant donné un ensemble $ L (v) $ couleurs pour chaque sommet $ v \ in g $ , existe-t-il une coloration de sommet adéquate, $ C $ C $ , de $ g $ , tel que $ C (v) \ inL (v), \ Forall V $ .

Je me demandais, pour des graphiques complets $ k_n $ , est la liste de coloriage NP-complet?Cela change si $ \ bigcup_ {v \ in k_n} l (v)={1,2 \ points n \} $ ?

Answer 1

Considérez la liste Colorant le graphe complet, où les couleurs disponibles pour Vertex $ v $ sont $ l (v) $ $.

former un graphique bipartite dans lequel le côté gauche correspond aux sommets et le côté droit correspond aux couleurs.Connectez $ v $ sur le côté gauche de toutes les couleurs de $ l (v) $ dans lecôté droit.

Il y a une liste Coloriage IFF Il y a une correspondance saturation du côté gauche.Vous pouvez décider si tel est le cas en exécutant un algorithme pour une correspondance parfaite bipartite.

Answer 2

Pour compléter la réponse de Yuval, le problème est résolu en polynôme-hétérogne plus généralement pour les graphiques de bloc qui généralisent des graphiques et des arbres complets.Voir l'algorithme de Jansen [1].

D'autre part, le problème (comme vous le savez probablement) reste NPC pour de nombreux graphiques qui sont proches d'être terminés dans un sens.Cela inclut des graphes bipartites complets, des graphiques complets moins un graphique fractionné correspondant et complet (voir [2, Tableau 1] pour un aperçu).

---

[1] Jansen, Klaus."Résultats de la complexité pour le problème optimal de la partition chromatique."Universitt¨at Trèves, Mathematik / Informatik, Forschungsbericht 96-41 (1996).

[2] Bonomo, Flavia, Guillermo Durán et Javier Marenco."Explorer la limite de complexité entre la coloration et la coloration de la liste."Annales des opérations Research 169.1 (2009): 3.