Gráfico bien coloreado
En la teoría de grafos , un subcampo de las matemáticas, un grafo bien coloreado es un grafo no dirigido para el cual la coloración codiciosa usa el mismo número de colores sin importar el 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 ciclo 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 una gráfica que no está bien coloreada es una ruta 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 los extremos de la ruta primero (usando el mismo color para cada extremo) hace que el algoritmo de coloración codicioso use tres colores para este gráfico. Debido a que existe un orden de vértice no óptimo, la ruta no está bien coloreada. [2] [3]
Un gráfico está bien coloreado si y solo si no tiene dos ordenamientos de vértices para los que el algoritmo de coloración codicioso 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, una gráfica tiene un número de Grundy o más si y solo si la gráfica obtenida al agregar una camarilla -vertex está bien coloreada. Por lo tanto, mediante una reducción del problema del número de Grundy, es NP-completo probar si existen estos dos ordenamientos. De ello se deduce que es co-NP-completo probar si un gráfico dado está bien coloreado. [1]
Un gráfico está hereditariamente bien coloreado si todos los subgrafos inducidos están bien coloreados. Las gráficas hereditariamente bien coloreadas son exactamente las cografías , las gráficas que no tienen una trayectoria de cuatro vértices como subgrafia inducida. [4]
