En teoría de grafos, un grafo perfecto es un grafo en el que el número cromático de cualquier subgrafo generado es igual al tamaño de la camarilla máxima de este subgrafo. Gracias al riguroso teorema del gráfico perfecto , se sabe desde 2002 que los gráficos perfectos son lo mismo que los gráficos de Berge . Un grafo G es un grafo de Berge si ni G ni su complemento han generado ciclos de longitud impar (5 o más aristas).
Los gráficos perfectos incluyen muchas familias importantes de gráficos y proporcionan la unificación de los resultados asociados con la coloración y las camarillas de estas familias. Por ejemplo, en todos los gráficos perfectos , el problema de coloración , el problema de la camarilla máxima y el problema del conjunto independiente máximo se pueden resolver en tiempo polinomial . Además, algunos teoremas minimax importantes de combinatoria , como el teorema de Dilworth , se pueden establecer en términos de gráficos perfectos y algunos gráficos relacionados.
La teoría de grafos perfectos ha sido desarrollada desde el trabajo de 1958 de Tibor Galai , que en lenguaje moderno puede interpretarse como la afirmación de que el complemento de un grafo bipartito es un grafo perfecto. Este resultado puede verse como un equivalente simple del teorema de König , un resultado mucho más temprano sobre coincidencias y coberturas de vértices en grafos bipartitos. El primer uso del término " gráfico perfecto " apareció en 1963 en un artículo de Claudy Berge , de donde proviene el nombre "gráficos de Berge". En este artículo, combinó el resultado de Galai con algunos resultados similares al definir gráficos perfectos y conjeturó que los gráficos perfectos y los gráficos de Berge son equivalentes. La conjetura fue probada en 2002 como un teorema de gráfico perfecto fuerte .
Algunas de las gráficas perfectas más conocidas son:
En todos los gráficos, el número de clique da el límite mínimo del número cromático, ya que en un clique todos los vértices deben estar coloreados en diferentes colores. Los gráficos perfectos son aquellos cuyo límite inferior es exacto no solo para todo el gráfico, sino también para todos sus subgráficos generados. Para gráficos que no son perfectos, el número cromático y el número de clique pueden diferir. Entonces, por ejemplo, para un ciclo de longitud 5, se necesitan 3 pinturas y la camarilla máxima tiene un tamaño de 2.
La prueba de que un gráfico es perfecto puede verse como el teorema minimax: el número mínimo de colores necesarios para colorear estos gráficos es igual al tamaño de la camarilla máxima. Muchos teoremas minimax importantes en combinatoria se pueden expresar en estos términos. Por ejemplo, el teorema de Dilworth establece que el número mínimo de cadenas al dividir un conjunto parcialmente ordenado en cadenas es igual al tamaño máximo de las anticadenas , y se puede reformular diciendo que los complementos de los gráficos de comparabilidad son perfectos. El teorema de Mirsky establece que el número mínimo de anticadenas al dividir en anticadenas es igual al tamaño máximo de las cadenas y corresponde de la misma manera a la perfección de los gráficos de comparabilidad.
La perfección de los gráficos de permutación equivale a decir que en cualquier secuencia de elementos ordenados, la longitud de la subsecuencia decreciente más grande es igual al número mínimo de secuencias cuando se divide en subsecuencias crecientes. El teorema de Erdős-Szekeres se deduce fácilmente de esta afirmación.
El teorema de König en teoría de grafos establece que la cobertura mínima de vértices de un gráfico bipartito corresponde a la coincidencia máxima y viceversa. Puede interpretarse como la perfección de los complementos de grafos bipartitos. Otro teorema sobre los gráficos bipartitos, que el índice cromático es igual al grado máximo del gráfico, equivale a la perfección del gráfico lineal de los gráficos bipartitos.
En su primer trabajo sobre grafos perfectos, Berge hizo dos importantes conjeturas sobre su estructura, que fueron demostradas más tarde.
El primero de estos teoremas fue el teorema del grafo perfecto de Laszlo Lovas (1972) que establece que un grafo es perfecto si y solo si su complemento es perfecto. Así, la perfección (definida como la igualdad del tamaño de la camarilla máxima y el número cromático en cualquier subgrafo generado) es equivalente al tamaño máximo del conjunto independiente y el número de cubiertas de camarilla.
El segundo teorema, enunciado por Berge como una conjetura, proporcionó una caracterización de grafos prohibidos para un grafo perfecto.
Un ciclo generado de longitud impar de al menos 5 se denomina agujero de longitud impar . El subgrafo generado complementario a un agujero impar se llama antiagujero impar . Un ciclo impar de longitud superior a 3 no puede ser perfecto, ya que su número cromático es tres y su número clique es dos. De manera similar, un gráfico de ciclo impar adicional de longitud 2k + 1 no puede ser perfecto porque su número cromático es k + 1 y su número de camarilla es k . (O la imperfección de este gráfico se deriva del teorema del gráfico perfecto y la imperfección de los complementos de los ciclos impares). Como estos gráficos no son perfectos, todo gráfico perfecto debe ser un gráfico de Berge , un gráfico sin agujeros impares y sin antiagujeros impares. Berge conjeturó que todo gráfico de Berge es perfecto. Esto finalmente se demuestra mediante el riguroso teorema del gráfico perfecto de Chudnovskaya , Robertson , Semur y Thomas (2006).
El teorema del gráfico perfecto tiene una demostración corta, pero la demostración del teorema del gráfico perfecto fuerte es larga y técnicamente difícil. Se basa en la descomposición estructural de grafos de Berge. Los métodos de descomposición relacionados también nacieron como resultado del estudio de otras clases de gráficos, en particular los gráficos sin garras .
Para todos los gráficos perfectos , el problema de coloración de gráficos, el problema de la camarilla máxima y el problema del conjunto independiente máximo se pueden resolver en tiempo polinomial (Grötschel, Lovász, Schrijver, 1988) [1] . El algoritmo de caso general usa el método del elipsoide para la programación lineal , pero los algoritmos combinatorios conocidos para muchos casos especiales son más eficientes.
Durante muchos años, la cuestión de la complejidad computacional de reconocer grafos de Berge y grafos perfectos permaneció abierta. De la definición de grafos de Berge se sigue inmediatamente que su reconocimiento es una tarea de la clase co-NP [2] . Finalmente, después de probar el teorema del gráfico perfecto fuerte, se encontró un algoritmo polinomial.