En la teoría de grafos , la extensión de precoloreado es el problema de extender la coloración de un gráfico de un subconjunto de los vértices de un gráfico, con un conjunto dado de colores, a una coloración de todo el gráfico que no asigna el mismo color a dos vértices adyacentes. .
La extensión de precoloreado tiene el problema habitual de coloreado de gráficos como un caso especial, en el que el subconjunto de vértices inicialmente coloreado está vacío; por lo tanto, es NP-completo . Sin embargo, también es NP-completo para algunas otras clases de gráficos en los que el problema habitual de coloreado de gráficos es más fácil. Por ejemplo, es NP-completo en los gráficos de torre , por lo que corresponde al problema de completar un cuadrado latino parcialmente lleno . [1]
El problema se puede resolver en tiempo polinomial para gráficos de ancho de árbol acotado , pero el exponente del polinomio depende del ancho de árbol. [2] [3] Puede resolverse en tiempo lineal para instancias de extensión de precoloring en las que tanto el número de colores como el ancho del árbol están acotados. [2]
La extensión de precoloreado puede verse como un caso especial de coloreado de listas , el problema de colorear un gráfico en el que no se han coloreado los vértices, pero cada vértice tiene asignada una lista de colores disponibles. Para transformar un problema de extensión de precoloreado en un problema de coloreado de lista, asigne a cada vértice no coloreado en el problema de extensión de precoloreado una lista de los colores que aún no utilizan sus vecinos coloreados inicialmente y luego elimine los vértices coloreados del gráfico.
Los rompecabezas de Sudoku se pueden modelar matemáticamente como instancias del problema de extensión de precoloreado en gráficos de Sudoku . [4] [5]