Teorema del grafo perfecto

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 solo si su grafo complementario también es perfecto. Este resultado había sido conjeturado por Berge  (1961, 1963), y a veces se lo 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 del grupo más grande es igual al número mínimo de colores en una coloración del subgrafo. Los grafos perfectos incluyen muchas clases de grafos importantes, entre ellos los grafos bipartitos , los grafos cordales y los grafos de comparabilidad .

El complemento de un grafo tiene una arista entre dos vértices si y solo si el grafo original no tiene una arista entre los mismos dos vértices. Por lo tanto, una clique en el grafo original se convierte en un conjunto independiente en el complemento y una coloración del grafo original se convierte en una cobertura de clique del complemento.

El teorema del grafo perfecto establece:

El complemento de una gráfica perfecta es perfecto.

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 camarillas.

Sea G un grafo de ciclo de longitud impar mayor que tres (un llamado "agujero impar"). Entonces G requiere al menos tres colores en cualquier coloración, pero no tiene triángulo, por lo que no es perfecto. Por 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 verdadera 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 en un agujero impar. Como establece el teorema del grafo perfecto fuerte , los agujeros impares y los antiagujeros impares resultan ser los subgrafos inducidos prohibidos mínimos para los grafos perfectos.

En un grafo bipartito no trivial, el número óptimo de colores es (por definición) dos, y (dado que los grafos bipartitos no tienen triángulos ) el tamaño máximo de camarilla también es dos. Además, cualquier subgrafo inducido de un grafo bipartito sigue siendo bipartito. Por lo tanto, los grafos bipartitos son perfectos. En los grafos bipartitos de n vértices , una cobertura de camarilla mínima toma la forma de una correspondencia 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 correspondencia. 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 independiente máximo en un grafo bipartito también es n  −  M , ^[2] un resultado que fue una inspiración importante para la formulación de Berge de la teoría de grafos perfectos.

El teorema de Mirsky, que caracteriza la altura de un conjunto parcialmente ordenado en términos de particiones en anticadenas, puede formularse como la perfección del grafo de comparabilidad del conjunto parcialmente ordenado, y el teorema de Dilworth, que caracteriza la anchura de un conjunto parcialmente ordenado en términos de particiones en cadenas, puede formularse como la perfección de los complementos de estos grafos. Por lo tanto, el teorema del grafo perfecto puede utilizarse para demostrar el teorema de Dilworth a partir de la demostración (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 grafo es perfecto, el grafo formado por este proceso de sustitución también es perfecto. ^[4] Cualquier proceso de sustitución de este tipo puede descomponerse en pasos repetidos de duplicación de un vértice. Si el vértice duplicado pertenece a una camarilla máxima del grafo, aumenta tanto el número de camarilla como el número cromático en uno. Si, por otro lado, el vértice duplicado no pertenece a una camarilla máxima, forme un grafo 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 grafo dado. Los vértices eliminados cumplen con cada camarilla máxima, por lo que H tiene número de camarilla y número cromático uno menos que el del grafo dado. Los vértices eliminados y la nueva copia del vértice duplicado pueden luego agregarse nuevamente 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 clique y el número cromático en cada subgrafo inducido del grafo dado, por lo que cada paso de duplicación preserva la perfección del grafo. ^[5]

Dado un grafo perfecto G , Lovász forma un grafo G * reemplazando cada vértice v por una camarilla de t _v vértices, donde t _v es el número de conjuntos independientes máximos distintos en G que contienen a v . Es posible corresponder cada uno de los conjuntos independientes máximos distintos en G con uno de los conjuntos independientes máximos en G *, de tal manera que los conjuntos independientes máximos elegidos en G * sean todos disjuntos y cada vértice de G * aparezca en un único conjunto elegido; es decir, G * tiene una coloración en la que cada clase de color es un conjunto independiente máximo. Necesariamente, esta coloración es una coloración óptima de G *. Como 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 independientes máximos. El conjunto correspondiente K de vértices en G (los vértices cuyas camarillas expandidas en G * intersecan a K *) es una camarilla en G con la propiedad de que interseca a todo conjunto independiente máximo en G . Por lo tanto, el grafo formado a partir de G eliminando K tiene un número de cobertura de camarilla como máximo uno menor que el número de camarilla de G , y un número de independencia como mínimo uno menor que el número de independencia de G , y el resultado se sigue por inducción sobre este número. ^[6]

El teorema del grafo perfecto fuerte de Chudnovsky et al. (2006) establece que un grafo es perfecto si y solo 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 del grafo, 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 .

• Berge, Claude (1961), "Färbung von Graphen, deren sämtliche beziehungsweise deren ungerade Kreise starr sind", Wissenschaftliche Zeitschrift der Martin-Luther-Universität Halle-Wittenberg, Mathematisch-naturwissenschaftliche Reihe (en alemán), 10 : 114.
• Berge, Claude (1963), "Gráficos perfectos", Six Papers on Graph Theory , Calcuta: Indian Statistical Institute, págs  . 1-21.
• Cameron, K.; Edmonds, J .; Lovász, L. (1986), "Una nota sobre gráficas perfectas", Periodica Mathematica Hungarica , 17 (3): 173– 175, doi :10.1007/BF01848646, MR  0859346, S2CID  121018903.
• Chudnovsky, Maria ; Robertson, Neil ; Seymour, Paul ; Thomas, Robin (2006), "El teorema del grafo perfecto fuerte", Anales de Matemáticas , 164 (1): 51– 229, arXiv : math/0212070 , doi :10.4007/annals.2006.164.51, MR  2233847, S2CID  119151552.
• Chudnovsky, Maria ; Robertson, Neil ; Seymour, Paul ; Thomas, Robin (2003), "Progreso en gráficos perfectos" (PDF) , Programación matemática , Serie B., 97 ( 1– 2): 405– 422, doi : 10.1007/s10107-003-0449-8 , MR  2004404.
• Gallai, Tibor (1958), "Máximo-mínimo Sätze über Graphen", Acta Mathematica Academiae Scientiarum Hungaricae (en alemán), 9 ( 3– 4): 395– 434, doi :10.1007/BF02020271, MR  0124238
• Golumbic, Martin Charles (1980), "3.2. El teorema del grafo perfecto", Algorithmic Graph Theory and Perfect Graphs , Nueva York: Academic Press, págs.  53– 58, ISBN 0-12-289260-7, Sr.  0562306.
• Kőnig, Dénes (1931), "Gráfok és mátrixok", Matematikai és Fizikai Lapok (en húngaro), 38 : 116– 119
• Lovász, László (1972a), "Hipergrafos normales y la conjetura del grafo perfecto", Matemáticas discretas , 2 (3): 253– 267, doi :10.1016/0012-365X(72)90006-4.
• Lovász, László (1972b), "Una caracterización de grafos perfectos", Journal of Combinatorial Theory , Serie B, 13 (2): 95– 98, doi :10.1016/0095-8956(72)90045-7.
• Reed, Bruce A. (2001), "De la conjetura al teorema", en Ramírez Alfonsín, Jorge L.; Reed, Bruce A. (eds.), Perfect Graphs , Wiley-Interscience Series on Discrete Mathematics and Optimization, Chichester: Wiley, pp.  13– 24, MR  1861356.