Tengo una pregunta historica.
Estoy tratando de determinar la referencia para el hecho de que la capacidad de coloración en 3 de los gráficos (alternativamente, la capacidad de coloración en para k ≥ 3 dada ) es NP-difícil.
La respuesta tentadora es "el documento original de Karp", pero eso está mal. Aquí hay un escaneo: Reducibilidad entre problemas combinatorios, Karp (1972) . Demuestra que el número cromático (Entrada: un gráfico. Salida: ) es difícil. Ese es un problema más difícil, y la reducción es diferente de la construcción estándar de gadgets (con 3 colores, verdadero, falso y suelo) que implica dureza de 3 colores.
Garey y Johnson, Computadoras e intractabilidad , tienen una coloración como [GT4] y se refieren a Karp (1972).
np-hardness
ho.history-overview
Thore Husfeldt
fuente
fuente
Respuestas:
László Lovász , Coverings and coloring of hypergraphs , Proceedings of the Fourth Southeastern Conference on Combinatorics, Graph Theory and Computing, Utilitas Math., Winnipeg, Man., 1973, pp. 3-12, demostró que el número cromático se reduce a 3- coloración.
Creo que esa es la primera prueba de la completitud NP de la capacidad de 3 coloraciones.
Aquí está el papel de Lovász; vea también la excelente explicación de Vašek Chvátal a la reducción de Lovász.
fuente
Aquí hay otro artículo de 1973 que demuestra que la 3-colorabilidad es NP-hard.
(Parece que Lovász y Stockmeyer obtuvieron sus resultados de forma independiente).
Actualización: ver comentarios a continuación.
fuente