El teorema del grafo perfecto de Lovash [1] [2] establece que un grafo no dirigido es perfecto si y solo si su complemento también es perfecto. Este enunciado se expresó en la forma de la conjetura de Berge [3] [4] y el enunciado a veces se denomina teorema del gráfico perfecto débil, para no confundirlo con el teorema del gráfico perfecto estricto [5] , que describe los gráficos perfectos por su subgrafos generados prohibidos .
Un grafo perfecto es un grafo no dirigido, en cualquier subgrafo generado en el cual el tamaño de su camarilla más grande es igual al número mínimo de colores de color del subgrafo . Los gráficos perfectos incluyen muchas clases importantes de gráficos, incluidos gráficos bipartitos , gráficos cordales y gráficos de comparabilidad .
El complemento de un grafo tiene una arista entre dos vértices si y solo si el grafo original no tiene tal arista. Así, la camarilla en el gráfico original se convierte en un conjunto independiente en el complemento, y la coloración del gráfico original se convierte en la cubierta de camarilla del complemento.
El teorema del grafo perfecto establece:
El complemento de un grafo perfecto es perfecto.Formulación equivalente: en un gráfico perfecto, el tamaño del conjunto independiente más grande es igual al número mínimo de clicas en la cubierta de clicas.
Sea G un gráfico-ciclo de longitud impar mayor que tres (el llamado “agujero impar”). Entonces, cada coloración de G requiere al menos tres colores, pero no hay triángulos, por lo que la gráfica no es perfecta. Por el teorema del gráfico perfecto, el complemento del gráfico G (el "antiagujero impar") también debe ser imperfecto. Si un grafo G es un ciclo de cinco vértices, es isomorfo a su complemento , pero esto no es cierto para ciclos más largos. Una tarea no trivial es calcular el número de camarilla y el número cromático en un antiagujero impar y un agujero impar. Como establece el estricto teorema del gráfico perfecto , los agujeros impares y los antiagujeros impares resultan ser los subgrafos inducidos mínimos prohibidos de los gráficos perfectos.
En un gráfico bipartito no trivial , el número óptimo de colores es (por definición) dos y (dado que los gráficos bipartitos no contienen triángulos ) el tamaño de camarilla más grande también es dos. Por lo tanto, cualquier subgrafo generado de un grafo bipartito permanece bipartito. Por lo tanto, los gráficos bipartitos son perfectos. En gráficos bipartitos con n vértices, la cobertura de camarilla más grande toma la forma de la coincidencia más grande , junto con una camarilla adicional para cada vértice descubierto de tamaño n − M , donde M es el número de elementos en la coincidencia. En este caso, el teorema del grafo perfecto implica el teorema de König de que el tamaño del conjunto máximo independiente en un grafo bipartito en un grafo bipartito también es n − M [6] , resultado que fue el principal impulso para la formulación de Berge del Teoría de grafos perfectos.
El teorema de Mirsky , que describe la altura de un poset en términos de partición en anticadenas , se puede formular como una perfección del gráfico de comparabilidad de un poset, y los teoremas de Dilworth , que describen el ancho de un poset en términos de partición en cadenas, puede formularse como una perfección de los complementos de estos gráficos. Por lo tanto, el teorema del grafo perfecto se puede utilizar para probar el teorema de Dilworth, basándose en la prueba (más simple) del teorema de Mirsky, o viceversa [7] .
Para probar el teorema en grafos perfectos, Lovash usó la operación de reemplazar vértices en un grafo por camarillas. Berge ya sabía que si la gráfica es perfecta, la gráfica obtenida por tal reemplazo también será perfecto [8] . Cualquier proceso de reemplazo de este tipo se puede dividir en pasos repetidos de duplicación de vértices. Si el vértice duplicado pertenece a la camarilla más grande del grafo, aumenta en uno el número de camarilla y el número cromático. Si, por el contrario, el vértice duplicado no pertenece a la camarilla más grande, forme el grafo H eliminando los vértices del mismo color que el duplicado (pero no el vértice duplicado en sí) de la coloración óptima del gráfico. Los vértices a eliminar están incluidos en todos los cliques más grandes, por lo que H tiene el número de cliques y el número cromático uno menos que en el gráfico original. Los vértices eliminados y las nuevas copias de los vértices duplicados se pueden agregar a una sola clase de color, lo que demuestra que el paso de duplicación no cambia el número cromático. Los mismos argumentos muestran que la duplicación mantiene el número de camarillas igual al número cromático en cada subgrafo generado del gráfico dado, de modo que cada paso de duplicación mantiene el gráfico perfecto [9] .
Dado un gráfico perfecto G , Lovash genera un gráfico G * reemplazando cada vértice v con una camarilla con t v vértices, donde t v es el número de conjuntos distintos máximos distintos en G que contienen v . Se puede asociar a cada uno de los varios conjuntos independientes máximos en G un conjunto independiente máximo en G * de tal manera que los conjuntos independientes en G * son todos disjuntos y cada vértice de G * aparece en el único conjunto elegido. Es decir, G * tiene una coloración en la que cada clase de color es un conjunto máximo independiente. Necesariamente, esta coloración será una coloración óptima de G *. Dado que G es perfecto, también lo es G *, y luego tiene una camarilla máxima K * cuyo tamaño es igual al número de colores en este coloreado, que es igual al número de diferentes conjuntos máximos independientes en G . Necesariamente, K * contiene una representación diferente para cada uno de estos conjuntos máximos. El correspondiente conjunto K de vértices en G (vértices cuyas camarillas extendidas en G * se cruzan con K *) es una camarilla en G con la propiedad de que se cruza con cualquier conjunto independiente máximo en G. Por lo tanto, el gráfico formado a partir de G eliminando K tiene un número de cobertura de camarilla no mayor que el número de camarilla de G sin uno, y el número de independencia es al menos uno menos que el número de independencia de G. El resultado se sigue de la inducción sobre este número [10]
El teorema fuerte sobre grafos perfectos de Chudnovskaya, Robertson, Seymour y Thomas [11] establece que un grafo es perfecto si y solo si ninguno de los subgrafos generados es un ciclo de longitud impar mayor o igual a cinco, y tampoco es el complemento de tal ciclo. Dado que tal descripción es insensible a la operación del complemento del gráfico, el teorema del gráfico perfecto débil se sigue de inmediato.
Cameron, Edmonds y Lovasz [12] demostraron que si las aristas de un gráfico completo se dividen en tres subgráficos de tal manera que tres vértices cualesquiera generen un gráfico conectado en uno de los tres subgráficos, y si dos de los subgráficos son perfectos , entonces el tercer subgrafo también es perfecto. El teorema del gráfico perfecto es un caso especial de este resultado cuando uno de los tres gráficos es el gráfico vacío .