En teoría de grafos , el teorema del grafo perfecto de László Lovász (1972a, 1972b) establece que un grafo no dirigido es perfecto si y sólo si su grafo complementario también es perfecto. Este resultado había sido conjeturado por Berge (1961, 1963), y a veces se le llama teorema del grafo perfecto débil para distinguirlo del teorema del grafo perfecto fuerte [1] que caracteriza a los grafos perfectos por sus subgrafos inducidos prohibidos .
Un grafo perfecto es un grafo no dirigido con la propiedad de que, en cada uno de sus subgrafos inducidos , el tamaño de la camarilla más grande es igual al número mínimo de colores en una coloración del subgrafo. Los gráficos perfectos incluyen muchas clases de gráficos importantes, incluidos gráficos bipartitos , gráficos cordales y gráficos de comparabilidad .
El complemento de un gráfico tiene una arista entre dos vértices si y sólo si el gráfico original no tiene una arista entre los mismos dos vértices. Así, una camarilla en el gráfico original se convierte en un conjunto independiente en el complemento y una coloración del gráfico original se convierte en una cubierta de camarilla del complemento.
El teorema del grafo perfecto establece:
De manera equivalente, en un gráfico perfecto, el tamaño del conjunto independiente máximo es igual al número mínimo de camarillas en una cobertura de camarilla.
Sea G un gráfico de ciclo de longitud impar mayor que tres (el llamado "agujero impar"). Entonces G requiere al menos tres colores de cualquier coloración, pero no tiene triángulo, por lo que no es perfecto. Según el teorema del grafo perfecto, el complemento de G (un "antiagujero impar") tampoco debe ser perfecto. Si G es un ciclo de cinco vértices, es isomorfo a su complemento , pero esta propiedad no es cierta para ciclos impares más largos, y no es tan trivial calcular el número de camarilla y el número cromático en un antiagujero impar como lo es en un agujero extraño. Como establece el teorema del grafo perfecto fuerte , los agujeros impares y los antiagujeros impares resultan ser los subgrafos inducidos mínimos prohibidos para los grafos 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 tienen triángulos ) el tamaño máximo de camarilla también es dos. Además, cualquier subgrafo inducido de un gráfico bipartito sigue siendo bipartito. Por tanto, las gráficas bipartitas son perfectas. En gráficos bipartitos de n -vértices, una cobertura de camarilla mínima toma la forma de una coincidencia máxima junto con una camarilla adicional para cada vértice no coincidente, con tamaño n − M , donde M es la cardinalidad de la coincidencia. Por lo tanto, en este caso, el teorema del grafo perfecto implica el teorema de Kőnig de que el tamaño de un conjunto máximo independiente en un gráfico bipartito también es n − M , [2] un resultado que fue una gran inspiración para la formulación de Berge de la teoría de los grafos perfectos. .
El teorema de Mirsky que caracteriza la altura de un conjunto parcialmente ordenado en términos de particiones en anticadenas se puede formular como la perfección del gráfico de comparabilidad de un conjunto parcialmente ordenado, y el teorema de Dilworth que caracteriza el ancho de un conjunto parcialmente ordenado en términos de particiones en cadenas puede formularse como la perfección de los complementos de estos gráficos. Por tanto, el teorema del grafo perfecto se puede utilizar para demostrar el teorema de Dilworth a partir de la prueba (mucho más sencilla) del teorema de Mirsky, o viceversa. [3]
Para demostrar el teorema del grafo perfecto, Lovász utilizó una operación de sustitución de vértices en un grafo por camarillas; Berge ya sabía que, si un gráfico es perfecto, el gráfico formado por este proceso de sustitución también lo es. [4] Cualquier proceso de reemplazo de este tipo puede dividirse en pasos repetidos de duplicación de un vértice. Si el vértice duplicado pertenece a una camarilla máxima del gráfico, aumenta en uno tanto el número de camarilla como el número cromático. Si, por otro lado, el vértice duplicado no pertenece a una camarilla máxima, forme un gráfico H eliminando los vértices con el mismo color que el vértice duplicado (pero no el vértice duplicado en sí) de una coloración óptima del gráfico dado. . Los vértices eliminados cumplen con cada camarilla máxima, por lo que H tiene un número de camarilla y un número cromático uno menor que el del gráfico dado. Los vértices eliminados y la nueva copia del vértice duplicado se pueden volver a agregar como una sola clase de color, lo que demuestra que en este caso el paso de duplicación deja el número cromático sin cambios. El mismo argumento muestra que la duplicación preserva la igualdad del número de camarilla y el número cromático en cada subgrafo inducido del gráfico dado, por lo que cada paso de duplicación preserva la perfección del gráfico. [5]
Dado un gráfico perfecto G , Lovász forma un gráfico G * reemplazando cada vértice v por una camarilla de t v vértices, donde t v es el número de conjuntos máximos independientes distintos en G que contienen v . Es posible corresponder cada uno de los distintos conjuntos máximos independientes en G con uno de los conjuntos máximos independientes en G *, de tal forma que los conjuntos máximos independientes elegidos en G * sean todos disjuntos y cada vértice de G * aparezca en un conjunto elegido único; es decir, G * tiene una coloración en la que cada clase de color es un conjunto máximo independiente. Necesariamente, esta coloración es una coloración óptima de G *. Debido a que G es perfecto, también lo es G *, y por lo tanto tiene una camarilla máxima K * cuyo tamaño es igual al número de colores en esta coloración, que es el número de conjuntos independientes máximos distintos en G ; necesariamente, K * contiene un representante distinto para cada uno de estos conjuntos máximos independientes. El correspondiente conjunto K de vértices en G (los vértices cuyas camarillas expandidas en G * intersectan K *) es una camarilla en G con la propiedad de que interseca cada conjunto máximo independiente en G . Por lo tanto, el gráfico formado a partir de G eliminando K tiene un número de cobertura de camarilla como máximo uno menos que el número de camarilla de G y un número de independencia al menos uno menor que el número de independencia de G , y el resultado se sigue por inducción de este número. [6]
El teorema del gráfico perfecto fuerte de Chudnovsky et al. (2006) afirma que un gráfico es perfecto si y sólo si ninguno de sus subgrafos inducidos son ciclos de longitud impar mayor o igual a cinco, o sus complementos. Debido a que esta caracterización no se ve afectada por la complementación de grafos, implica inmediatamente el teorema del grafo perfecto débil.
Cameron, Edmonds y Lovász (1986) demostraron que, si las aristas de un grafo completo se dividen en tres subgrafos de tal manera que cada tres vértices inducen un grafo conexo en uno de los tres subgrafos, y si dos de los subgrafos son perfectos , entonces el tercer subgrafo también es perfecto. El teorema del grafo perfecto es el caso especial de este resultado cuando uno de los tres subgrafos es el grafo vacío .