Grafo perfecto

En teoría de grafos, un grafo perfecto es un grafo en el que el número cromático de cada subgrafo inducido es igual al tamaño del mayor clique de ese subgrafo.

En cualquier grafo, el número clique provee una cota inferior para el número cromático, ya que a cada uno de los vértices en un clique se les debe asignar un color distinto para obtener una coloración propia. Los grafos perfectos son aquellos para los cuales esta cota inferior es exacta no sólo para el grafo en sí, sino para todos los subgrafos inducidos. En los grafos en general, el número cromático y el número de clique pueden ser distintos. Por ejemplo, un ciclo de 5 vértices requiere tres colores para obtener una coloración correcta, pero el clique mayor es de tamaño dos.

Los grafos perfectos incluyen varias familias de grafos importantes, y sirven para unificar resultados relacionados con la coloración y los cliques en esas familias. Por ejemplo, en todos los grafos perfectos, el problema de coloración de grafos, el problema de clique máximo y el problema del máximo conjunto independiente pueden ser resueltos en tiempo polinómico (Grötschel, Lovász y Schrijver, 1988). Además, varios teoremas min-max importantes de combinatoria como el teorema de Dilworth, pueden ser expresados en términos de la perfección de ciertos grafos asociados.

La teoría de grafos perfectos fue desarrollada a partir de un resultado obtenido en 1958 por Tibor Gallai que en lenguaje moderno puede ser interpretado de modo que el complementario de un grafo bipartito es perfecto. Este resultado puede ser visto también como un equivalente simple del teorema de König, un resultado anterior que relaciona emparejamientos con cobertura de vértices en grafos bipartitos. El primer uso de la frase "grafo perfecto" parece estar en un paper de 1963 publicado por Claude Berge. En este paper, Berge unió el resultado de Gallai con varios otros resultados similares, definiendo los grafos perfectos y conjeturando una caracterización de esos grafos que luego fue probado como el Teorema fuerte de los grafos perfectos.

Algunos de los grafos perfectos más conocidos son:

La caracterización de los grafos perfectos fue un problema que llevó tiempo resolver. Un avance importante fue la respuesta afirmativa a la entonces conjetura de los grafos perfectos.

Teorema de los grafos perfectos. (Lovász 1972)

Un ciclo inducido de longitud impar mayor o igual a 5 es llamado agujero impar. Un subgrafo inducido complemento de un agujerio impar es llamado un antiagujero impar. Un grafo que no contiene agujeros impares ni sus complementos es llamado grafo de Berge. Como consecuencia del teorema de los grafos perfectos, un grafo perfecto es necesariamente un grafo de Berge, pero probar si lo inverso era cierto fue algo muy difícil. A esta afirmación difícil de probar se la conocía como la conjetura fuerte de los grafos perfectos, y finalmente pudo se probada afirmativamente en mayo de 2002.

Teorema fuerte de los grafos perfectos. (Chudnovsky, Robertson, Seymour, Thomas 2002)

Como muchos otros resultados obtenido a partir de métodos estructurados, la prueba del teorema es larga y muy técnica. Los esfuerzos para resolver el problema permitieron avanzar en mayor profundidad la teoría de grafos, donde muchos problemas aún están abiertos. Por ejemplo, se pudo probar que el problema de reconocer grafos de Berge es co-NP (Lovász 1983), pero no se sabía si tenía o no complejidad P hasta que apareció la prueba del teorema fuerte de los grafos perfectos. Un algoritmo de tiempo polinómico fue descubierto poco después por Chudnovsky, Cornuéjols, Liu, Seymour, and Vušković, sin utilizar el teorema de los grafos perfectos.

---