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 el coloreado voraz utiliza la misma cantidad de colores independientemente del orden en que se eligen los colores para sus vértices. Es decir, para estos grafos, el número cromático (número mínimo de colores) y el número de Grundy (número máximo de colores elegidos vorazmente) 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 sencillo de un grafo que no está bien coloreado es un camino de cuatro vértices. Colorear los vértices en el orden del camino utiliza dos colores, lo cual es óptimo para este grafo. Sin embargo, si se colorean primero los extremos del camino (usando el mismo color para cada extremo), el algoritmo de coloración voraz utiliza tres colores para este grafo. Debido a que existe un ordenamiento de vértices no óptimo, el camino no está bien coloreado. ^{[ 2 ] [ 3 ]}

Un grafo está bien coloreado si y solo si no tiene dos ordenaciones de vértices para las cuales el algoritmo de coloración voraz produce diferentes números de colores. Por lo tanto, el reconocimiento de grafos no bien coloreados se puede realizar dentro de la clase de complejidad NP . Por otro lado, un grafo${\displaystyle G}$tiene el número Grundy${\displaystyle k}$o más si y solo si el gráfico obtenido de${\displaystyle G}$agregando un${\displaystyle (k-1)}$El clique de vértices está bien coloreado. Por lo tanto, mediante una reducción del problema del número de Grundy, es NP-completo comprobar si existen estos dos ordenamientos. De ello se deduce que es co-NP-completo comprobar si un grafo dado está bien coloreado. ^{[ 1 ]}

Un grafo es hereditariamente bien coloreado si cada subgrafo inducido es bien coloreado. Los grafos hereditariamente bien coloreados son precisamente los cografos , los grafos que no tienen un camino de cuatro vértices como subgrafo inducido. ^{[ 4 ]}