En la teoría de grafos, un gráfico bien ordenado es un gráfico cuyos vértices se pueden ordenar de tal manera que el algoritmo de coloración codicioso con este ordenamiento colorea de manera óptima cualquier subgráfico generado del gráfico dado. El orden correspondiente se llama perfecto . Los gráficos completamente ordenables forman una subclase de gráficos perfectos, y esta subclase incluye gráficos cordales, gráficos de comparabilidad y gráficos heredados de la distancia . Sin embargo, verificar si un gráfico es completamente ordenable es un problema NP-completo .
El algoritmo de coloreo voraz, cuando se aplica a un ordenamiento dado de los vértices de un grafo G , considera los vértices del grafo secuencialmente (según el orden) y asigna a cada vértice el primer color disponible. Diferentes ordenaciones de vértices pueden resultar en diferentes números de colores requeridos. Siempre hay un orden que conduce a una coloración óptima; esto es cierto, por ejemplo, cuando se ordenan los vértices de acuerdo con los colores de la coloración óptima, pero tal ordenación puede resultar difícil de encontrar. Los gráficos bien ordenados, por definición, son gráficos para los que existe un orden que es óptimo para el algoritmo de coloreo voraz, no solo para el gráfico en sí, sino también para todos sus subgráficos generados .
Más formalmente, se dice que un grafo G es completamente ordenable si existe un ordenamiento π de los vértices de G tal que cualquier subgrafo generado de G esté coloreado de manera óptima por el algoritmo de coloración codicioso utilizando la subsecuencia de ordenamiento π generada por los vértices del subgrafo . Un orden π tiene esta propiedad exactamente cuando no hay cuatro vértices a , b , c y d para los cuales abcd es un subgrafo generado en el que a viene antes de b (en el orden) y c viene después de d [1] [2 ] .
El reconocimiento de grafos bien ordenados es un problema NP-completo [3] [2] . Sin embargo, es fácil verificar si un orden particular satisface la perfección (es decir, satisface los requisitos para un gráfico completamente ordenable). Por lo tanto, es un problema NP-difícil encontrar un orden perfecto de un gráfico, incluso si se sabe de antemano que el gráfico está completamente ordenado.
Cualquier gráfico completamente ordenable es perfecto . [1] [2]
Los gráficos de cuerdas son completamente ordenables. El orden perfecto de los gráficos cordales se puede encontrar invirtiendo el orden de excepción perfecto para el gráfico. Por lo tanto, la aplicación del algoritmo de coloración voraz a un ordenamiento perfecto proporciona un algoritmo de coloración eficiente para grafos cordales. Los gráficos de comparabilidad también son completamente ordenables, donde el ordenamiento perfecto está determinado por el orden topológico de la orientación transitiva del gráfico [1] [2] .
Otra clase de grafos bien ordenados consiste en grafos G tales que en cualquier subconjunto de cinco vértices en G , al menos uno de los cinco vértices tiene una vecindad cerrada , que es un subconjunto de (o igual a) las vecindades cerradas del otro vértices en los cinco primeros. Equivalentemente, se trata de grafos en los que el orden parcial de vecindades cerradas definido por la inclusión de conjuntos tiene un ancho máximo de 4. Un grafo de ciclo con 5 vértices tiene un orden de vecindad parcial de ancho igual a cinco, por lo que cuatro es el ancho máximo que proporciona un ordenamiento perfecto. Como en el caso de grafos cordales (pero, en general, no para grafos completamente ordenables en general), los grafos de ancho cuatro se reconocen en tiempo polinomial [4] [5] .
El concepto entre el orden de eliminación perfecto para grafos cordales y el orden perfecto es la noción de orden de eliminación semiperfecto . En el concepto de eliminación perfecta, no hay un camino generado de 3 vértices en el que se elimine primero el vértice central, y en el orden de eliminación semiperfecto, no hay un camino generado de 4 vértices en el que uno de los vértices medios se elimine antes los otros de los cuatro. La inversión de tal ordenamiento satisface así los requisitos de un ordenamiento perfecto, de modo que los gráficos con un orden de eliminación semiperfecto son completamente ordenables [6] [7] . En particular, el algoritmo de búsqueda lexicográfico de amplitud primero utilizado para encontrar el orden de exclusión perfecto para grafos cordales se puede usar para encontrar el orden de exclusión semiperfecto de grafos heredados de la distancia , que también son completamente ordenables [8] .
Los grafos para los que cualquier orden de vértices es perfecto son los cografos , que son tanto cordales como grafos heredados de la distancia [9] . Debido a que los cografos no contienen caminos generados de cuatro vértices, no pueden violar el requisito de que los caminos estén ordenados en perfecto orden.
Se conocen algunas otras clases de gráficos completamente ordenables [10] [6] [11] [2] [12] .