Teorema del grafo perfecto fuerte

En teoría de grafos , el teorema del grafo perfecto fuerte es una caracterización prohibida de los grafos perfectos como aquellos que no tienen ni agujeros impares ( ciclos inducidos de longitud impar de longitud al menos 5) ni antiagujeros impares (complementos de agujeros impares). Fue conjeturado por Claude Berge en 1961. Una demostración realizada por Maria Chudnovsky , Neil Robertson , Paul Seymour y Robin Thomas fue anunciada en 2002 ^{[ 1 ]} y publicada por ellos en 2006.

La demostración del teorema del grafo perfecto fuerte les valió a sus autores un premio de 10 000 dólares ofrecido por Gérard Cornuéjols de la Universidad Carnegie Mellon ^{[ 2 ]} y el Premio Fulkerson de 2009. ^{[ 3 ]}

Un grafo perfecto es aquel en el que, para cada subgrafo inducido , el tamaño de la clique máxima es igual al número mínimo de colores en una coloración del grafo. Los grafos perfectos incluyen muchas clases de grafos bien conocidas, como los grafos bipartitos , los grafos cordales y los grafos de comparabilidad . En sus trabajos de 1961 y 1963, donde definió por primera vez esta clase de grafos, Claude Berge observó que es imposible que un grafo perfecto contenga un agujero impar, un subgrafo inducido con la forma de un grafo cíclico de longitud impar de cinco o más, porque los agujeros impares tienen número de clique dos y número cromático tres. De manera similar, observó que los grafos perfectos no pueden contener antiagujeros impares, subgrafos inducidos complementarios a los agujeros impares: un antiagujero impar con 2k +  1  vértices tiene número de clique k y número cromático k  +  1, lo cual también es imposible para los grafos perfectos. Los grafos que no tienen ni agujeros impares ni antiagujeros impares se conocieron como grafos de Berge.

Berge conjeturó que todo grafo de Berge es perfecto, o, equivalentemente, que los grafos perfectos y los grafos de Berge definen la misma clase de grafos. Esto se conoció como la conjetura del grafo perfecto fuerte, hasta su demostración en 2002, cuando se le cambió el nombre a teorema del grafo perfecto fuerte.

Otra conjetura de Berge, demostrada en 1972 por László Lovász , afirma que el complemento de todo grafo perfecto también es perfecto. Esto se conoce como el teorema del grafo perfecto o, para distinguirlo de la conjetura/teorema del grafo perfecto fuerte, el teorema del grafo perfecto débil. Dado que la caracterización de grafos prohibidos de Berge es autocomplementaria, el teorema del grafo perfecto débil se deduce inmediatamente del teorema del grafo perfecto fuerte.

La demostración del teorema del grafo perfecto fuerte por Chudnovsky et al. sigue un esquema conjeturado en 2001 por Conforti, Cornuéjols, Robertson, Seymour y Thomas, según el cual todo grafo de Berge forma uno de cinco tipos de bloques de construcción básicos (clases especiales de grafos perfectos) o tiene uno de cuatro tipos diferentes de descomposición estructural en grafos más simples. Un grafo de Berge mínimamente imperfecto no puede tener ninguna de estas descomposiciones, de lo cual se deduce que no puede existir ningún contraejemplo al teorema. ^{[ 4 ]} Esta idea se basó en conjeturas previas de descomposiciones estructurales de tipo similar que habrían implicado la conjetura del grafo perfecto fuerte, pero que resultaron ser falsas. ^{[ 5 ]}

Las cinco clases básicas de grafos perfectos que forman el caso base de esta descomposición estructural son los grafos bipartitos, los grafos de líneas de grafos bipartitos, los grafos complementarios de grafos bipartitos, los complementos de grafos de líneas de grafos bipartitos y los grafos doblemente divididos. Es fácil ver que los grafos bipartitos son perfectos: en cualquier subgrafo inducido no trivial, el número de clique y el número cromático son ambos dos y, por lo tanto, iguales. La perfección de los complementos de grafos bipartitos, y de los complementos de grafos de líneas de grafos bipartitos, es equivalente al teorema de Kőnig que relaciona los tamaños de los emparejamientos máximos , los conjuntos independientes máximos y las coberturas de vértices mínimas en grafos bipartitos. La perfección de los grafos de líneas de grafos bipartitos puede enunciarse equivalentemente como el hecho de que los grafos bipartitos tienen un índice cromático igual a su grado máximo , demostrado por Kőnig (1916) . Por lo tanto, estas cuatro clases básicas son perfectas. Los grafos doblemente divididos son parientes de los grafos divididos que también pueden demostrarse que son perfectos. ^{[ 6 ]}

Los cuatro tipos de descomposiciones consideradas en esta demostración son las 2-uniones, los complementos de las 2-uniones, las particiones sesgadas equilibradas y los pares homogéneos.

Una 2-unión es una partición de los vértices de un grafo en dos subconjuntos, con la propiedad de que las aristas que unen estos dos subconjuntos forman dos grafos bipartitos completos disjuntos en vértices . Cuando un grafo tiene una 2-unión, puede descomponerse en subgrafos inducidos llamados "bloques", reemplazando uno de los dos subconjuntos de vértices por un camino más corto dentro de ese subconjunto que conecta uno de los dos grafos bipartitos completos con el otro; cuando no existe tal camino, el bloque se forma reemplazando uno de los dos subconjuntos de vértices por dos vértices, uno por cada subgrafo bipartito completo. Una 2-unión es perfecta si y solo si sus dos bloques son perfectos. Por lo tanto, si un grafo mínimamente imperfecto tiene una 2-unión, debe ser igual a uno de sus bloques, de lo cual se deduce que debe ser un ciclo impar y no un grafo de Berge. Por la misma razón, un grafo mínimamente imperfecto cuyo complemento tiene una 2-unión no puede ser un grafo de Berge. ^{[ 7 ]}

Una partición sesgada es una partición de los vértices de un grafo en dos subconjuntos, uno de los cuales induce un subgrafo disconexo y el otro tiene un complemento disconexo; Chvátal (1985) conjeturó que ningún contraejemplo mínimo a la conjetura del grafo perfecto fuerte podría tener una partición sesgada. Chudnovsky et al. introdujeron algunas restricciones técnicas sobre las particiones sesgadas y pudieron demostrar que la conjetura de Chvátal es cierta para las "particiones sesgadas balanceadas" resultantes. La conjetura completa es un corolario del teorema del grafo perfecto fuerte. ^{[ 8 ]}

Un par homogéneo está relacionado con una descomposición modular de un grafo. Es una partición del grafo en tres subconjuntos V ₁ , V ₂ , y V ₃ tales que V ₁ y V ₂ juntos contienen al menos tres vértices, V ₃ contiene al menos dos vértices, y para cada vértice v en V ₃ y cada i en {1,2} o bien v es adyacente a todos los vértices en V _i o a ninguno de ellos. No es posible que un grafo mínimamente imperfecto tenga un par homogéneo. ^{[ 9 ]} Posteriormente a la demostración de la conjetura del grafo perfecto fuerte, Chudnovsky (2006) la simplificó mostrando que los pares homogéneos podían eliminarse del conjunto de descomposiciones utilizadas en la demostración.

La prueba de que cada grafo de Berge pertenece a una de las cinco clases básicas o tiene uno de los cuatro tipos de descomposición sigue un análisis de casos, según si existen ciertas configuraciones dentro del grafo: un "estirador", un subgrafo que puede descomponerse en tres caminos inducidos sujetos a ciertas restricciones adicionales, el complemento de un estirador y una "rueda propia", una configuración relacionada con un grafo de rueda , que consiste en un ciclo inducido junto con un vértice central adyacente a al menos tres vértices del ciclo y que obedece varias restricciones adicionales. Para cada posible elección de si existe un estirador o su complemento o una rueda propia dentro del grafo de Berge dado, se puede demostrar que el grafo está en una de las clases básicas o que es descomponible. ^{[ 10 ]} Este análisis de casos completa la prueba.

• Berge, Claude (1961), "Färbung von Graphen, deren sämtliche bzw. deren ungerade Kreise starr sind", Wiss. Z. Martin-Luther-Univ. Halle-Wittenberg Math.-Natur. Reihe , 10 : 114.
• Berge, Claude (1963), "Gráficos perfectos", Seis artículos sobre teoría de grafos , Calcuta: Instituto Estadístico Indio, págs . 1–21 .
• Chudnovsky, Maria (2006), "Trígrafos de Berge", Journal of Graph Theory , 53 (1): 1– 55, doi : 10.1002/jgt.20165 , MR 2245543 .
• Chudnovsky, Maria ; Robertson, Neil ; Seymour, Paul ; Thomas, Robin (2006), "El teorema del grafo perfecto fuerte" , Annals of Mathematics , 164 (1): 51–229 , arXiv : math/0212070 , doi : 10.4007/annals.2006.164.51 , MR 2233847 .
• Chudnovsky, Maria ; Robertson, Neil ; Seymour, Paul ; Thomas, Robin (2003), "Progress on perfect graphs", Mathematical Programming , Serie B, 97 ( 1–2 ): 405–422 , CiteSeerX 10.1.1.137.3013 , doi : 10.1007/s10107-003-0449-8 , MR 2004404  .
• Chvátal, Václav (1985), "Star-cutsets and perfect graphs", Journal of Combinatorial Theory , Serie B, 39 (3): 189–199 , doi : 10.1016/0095-8956(85)90049-8 , MR 0815391 .
• Chvátal, Václav ; Sbihi, Najiba (1987), "Los grafos de Berge sin toros son perfectos", Graphs and Combinatorics , 3 (2): 127–139 , doi : 10.1007/BF01788536 , MR 0932129 .
• Cornuéjols, Gérard (2002), "La conjetura del grafo perfecto fuerte", Actas del Congreso Internacional de Matemáticos, Vol. III (Pekín, 2002) (PDF) , Pekín: Higher Ed. Press, pp. 547–559 , MR 1957560  .
• Cornuéjols, G.; Cunningham, WH (1985), "Composiciones para grafos perfectos", Matemáticas Discretas , 55 (3): 245– 254, doi : 10.1016/S0012-365X(85)80001-7 , MR 0802663 .
• Hougardy, S. (1991), Contraejemplos a tres conjeturas sobre grafos perfectos , Informe técnico RR870-M, Grenoble, Francia: Laboratoire Artemis-IMAG, Universitá Joseph Fourier. Citado por Roussel, Rusu y Thuillier (2009) .
• Kőnig, Dénes (1916), "Gráfok és alkalmazásuk a determinánsok és a halmazok elméletére", Matematikai és Természettudományi Értesítő , 34 : 104– 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.
• Mackenzie, Dana (5 de julio de 2002), "Matemáticas: La teoría de grafos descubre las raíces de la perfección", Science , 297 (5578): 38, doi : 10.1126/science.297.5578.38 , PMID 12098683 .
• Reed, BA (1986), Un teorema semifuerte de grafos perfectos , tesis doctoral, Montreal, Quebec, Canadá: Departamento de Ciencias de la Computación, Universidad McGill.. Citado por Roussel, Rusu y Thuillier (2009) .
• Roussel, F.; Rusu, I.; Thuillier, H. (2009), "La conjetura del grafo perfecto fuerte: 40 años de intentos y su resolución", Discrete Mathematics , 309 (20): 6092– 6113, doi : 10.1016/j.disc.2009.05.024 , MR 2552645 .
• Rusu, Irena (1997), "Construyendo contraejemplos", Matemáticas Discretas , 171 ( 1–3 ): 213–227 , doi : 10.1016/S0012-365X(96)00081-7 , MR 1454452 .
• Seymour, Paul (2006), "Cómo se encontró la prueba de la conjetura del grafo perfecto fuerte" (PDF) , Gazette des Mathématiciens (109): 69–83 , MR 2245898 .

• El teorema del grafo perfecto fuerte , Václav Chvátal
• Weisstein, Eric W. "Teorema del grafo perfecto fuerte" . MathWorld .