En teoría de grafos , el teorema del grafo perfecto fuerte es una caracterización prohibida de los grafos perfectos como los grafos que no tienen agujeros impares ( ciclos inducidos por longitud impar de al menos 5) ni antiagujeros impares (complementos de agujeros impares). Fue conjeturado por Claude Berge en 1961. Una prueba de Maria Chudnovsky , Neil Robertson , Paul Seymour y Robin Thomas fue anunciada en 2002 [1] y publicada por ellos en 2006.
La prueba del teorema del grafo perfecto fuerte le 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 2009. [3]
Un grafo perfecto es un grafo en el que, para cada subgrafo inducido , el tamaño de la camarilla 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, incluyendo los grafos bipartitos , grafos cordales y grafos de comparabilidad . En sus trabajos de 1961 y 1963 que definen por primera vez esta clase de grafos, Claude Berge observó que es imposible que un grafo perfecto contenga un agujero impar, un subgrafo inducido en forma de un grafo de ciclo de longitud impar de longitud cinco o más, porque los agujeros impares tienen el número de camarilla dos y el 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 2 k + 1 vértices tiene el número de camarilla k y el número cromático k + 1, lo que nuevamente es imposible para los grafos perfectos. Los grafos que no tienen agujeros impares ni antiagujeros impares se conocieron como los 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. Esta conjetura 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 , es que el complemento de todo grafo perfecto es también perfecto. Esto se conoció como el teorema del grafo perfecto o (para distinguirlo de la conjetura/teorema del grafo perfecto fuerte) el teorema del grafo perfecto débil. Debido a que la caracterización del grafo prohibido de Berge es autocomplementaria, el teorema del grafo perfecto débil se sigue inmediatamente del teorema del grafo perfecto fuerte.
La prueba del teorema del grafo perfecto fuerte de Chudnovsky et al. sigue un esquema conjeturado en 2001 por Conforti, Cornuéjols, Robertson, Seymour y Thomas, según el cual cada grafo de Berge forma uno de los cinco tipos de bloques básicos de construcción (clases especiales de grafos perfectos) o tiene uno de los 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 que se sigue que no puede existir ningún contraejemplo del teorema. [4] Esta idea se basó en descomposiciones estructurales conjeturadas previamente 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 lineales de grafos bipartitos, los grafos complementarios de grafos bipartitos, los complementos de grafos lineales de grafos bipartitos y los grafos de doble división. 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, son iguales. La perfección de los complementos de grafos bipartitos y de los complementos de grafos lineales de grafos bipartitos son ambas equivalentes al teorema de Kőnig que relaciona los tamaños de los emparejamientos máximos , los conjuntos independientes máximos y las coberturas mínimas de vértices en grafos bipartitos. La perfección de los grafos lineales de grafos bipartitos se puede enunciar de manera equivalente 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 gráficos de doble división son parientes de los gráficos divididos que también pueden demostrarse como perfectos. [6]
Los cuatro tipos de descomposiciones considerados en esta prueba son 2-joins, complementos de 2-joins, particiones sesgadas balanceadas y pares homogéneos.
Una 2-join es una partición de los vértices de un grafo en dos subconjuntos, con la propiedad de que las aristas que abarcan el corte entre estos dos subconjuntos forman dos grafos bipartitos completos disjuntos en sus vértices . Cuando un grafo tiene una 2-join, 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 en cambio reemplazando uno de los dos subconjuntos de vértices por dos vértices, uno para cada subgrafo bipartito completo. Una 2-join es perfecta si y solo si sus dos bloques son ambos perfectos. Por lo tanto, si un grafo mínimamente imperfecto tiene una 2-join, debe ser igual a uno de sus bloques, de lo que se sigue que debe ser un ciclo impar y no de Berge. Por la misma razón, un grafo mínimamente imperfecto cuyo complemento tiene una 2-join no puede ser de Berge. [7]
Una partición oblicua es una partición de los vértices de un grafo en dos subconjuntos, uno de los cuales induce un subgrafo desconectado y el otro tiene un complemento desconectado; Chvátal (1985) había conjeturado que ningún contraejemplo mínimo de la conjetura del grafo perfecto fuerte podría tener una partición oblicua. Chudnovsky et al. introdujeron algunas restricciones técnicas sobre las particiones oblicuas y pudieron demostrar que la conjetura de Chvátal es verdadera para las "particiones oblicuas 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 1 , V 2 y V 3 tales que V 1 y V 2 juntos contienen al menos tres vértices, V 3 contiene al menos dos vértices, y para cada vértice v en V 3 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 prueba 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 prueba.
La prueba de que todo grafo de Berge cae en una de las cinco clases básicas o tiene uno de los cuatro tipos de descomposición se obtiene a partir de un análisis de caso, según si existen ciertas configuraciones dentro del grafo: un "camilla", un subgrafo que puede descomponerse en tres caminos inducidos sujetos a ciertas restricciones adicionales, el complemento de una camilla, 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 de ciclo y que obedece a varias restricciones adicionales. Para cada posible elección de si existe una camilla 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 caso completa la prueba.