Complejidad de la lista Colorear $ k_n $ con $ n $ colores

Question

the Lista de problemas para colorear es, dado un conjunto $ L (v) $ colores para cada vértice $ v \ in g $ , ¿hay un colorante de vértice adecuado, $ C $ , de $ g $ , de modo que $ c (v) \ enL (v), \ forall v $ .

Me preguntaba, para completar los gráficos $ k_n $ , ¿es la lista para colorear NP-complete?¿Esto cambia si $ \ bigcup_ {v \ in k_n} l (v)={1,2 \ dots n \} $ ?

Answer 1

Considere la lista para colorear el gráfico completo, donde los colores disponibles para el vértice $ v $ son $ l (v) $.

Forma un gráfico bipartito en el que el lado izquierdo corresponde a los vértices y el lado derecho corresponde a los colores.Conecte $ V $ en el lado izquierdo a todos los colores en $ l (v) $ en ellado derecho.

Hay una lista para colorear IFF, hay una coincidencia que se sature el lado izquierdo.Puede decidir si este es el caso ejecutando un algoritmo para una coincidencia perfecta de bipartito.

Answer 2

Para complementar la respuesta de Yuval, el problema es solucionable en tiempo polinomial, más generalmente para gráficos de bloques que generalizan gráficos y árboles completos.Ver el algoritmo de jansen [1].

Por otro lado, el problema (como probablemente sepa) sigue siendo NPC para muchos gráficos que están cerca de estar completos en cierto sentido.Esto incluye gráficos de bipartito completos, gráficos completos menos un gráfico de división integrados y coincidentes (consulte [2, Tabla 1] para obtener una visión general).

---

[1] JANSEN, KLAUS."Resultados de la complejidad para el problema de la partición cromática del costo óptimo".Universit¨at Trier, Mathematik / Informatik, Forschungsbericht 96-41 (1996).

[2] Bonomo, Flavia, Guillermo Durán y Javier Marenco."Explorando el límite de la complejidad entre la coloración y el colorante de la lista".Anales de Investigación de Operaciones 169.1 (2009): 3.