En teoría de grafos , un subcampo de las matemáticas, un gráfico bien coloreado es un gráfico no dirigido para el cual la coloración codiciosa utiliza el mismo número de colores independientemente del orden en que se eligen los colores para sus vértices. Es decir, para estos gráficos, el número cromático (número mínimo de colores) y el número de Grundy (número máximo de colores elegidos con avidez) son iguales. [1]
Los gráficos bien coloreados incluyen los gráficos completos y los gráficos de ciclos de longitud impar (los gráficos que forman los casos excepcionales del teorema de Brooks ), así como los gráficos bipartitos completos y los gráficos multipartitos completos .
El ejemplo más simple de un gráfico que no está bien coloreado es un camino de cuatro vértices. Para colorear los vértices en el orden de la ruta se utilizan dos colores, el óptimo para este gráfico. Sin embargo, colorear primero los extremos del camino (usando el mismo color para cada extremo) hace que el algoritmo de coloración codiciosa use tres colores para este gráfico. Debido a que existe un orden de vértices no óptimo, el camino no está bien coloreado. [2] [3]
Un gráfico está bien coloreado si y sólo si no tiene dos ordenamientos de vértices para los cuales el algoritmo de coloración codiciosa produce diferentes números de colores. Por lo tanto, el reconocimiento de gráficos que no están bien coloreados se puede realizar dentro de la clase de complejidad NP . Por otro lado, un gráfico tiene un número de Grundy o más si y solo si el gráfico obtenido al agregar una camarilla de vértices está bien coloreado. Por lo tanto, mediante una reducción del problema numérico de Grundy, es NP-completo probar si estos dos ordenamientos existen. De ello se deduce que es co-NP-completo probar si un gráfico determinado está bien coloreado. [1]
Un gráfico está hereditariamente bien coloreado si cada subgrafo inducido está bien coloreado. Los gráficos hereditariamente bien coloreados son exactamente los cografos , los gráficos que no tienen una trayectoria de cuatro vértices como subgrafo inducido. [4]
