Grafo perfecto

El grafo Paley de orden 9, coloreado con tres colores, mostrando un clique de tres vértices. En este grafo y cada uno de sus subgrafos inducidos, el número cromático es igual al número de clique, por lo que es un 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 correcta. 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 polinomial (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 grafo complemento 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.

Familias de grafos que son perfectos

Algunos de los grafos perfectos más conocidos son:

• Grafos bipartitos
• Los grafos adjuntos a grafos bipartitos (ver Teorema de König)
• Grafos de intervalos (los vértices representan intervalos lineales, las aristas las intersecciones de a pares no vacías)
• Grafos cordales (cada ciclo de cuatro o más vértices tiene una cuerda, que es una arista entre dos nodos que no son adyacentes dentro del ciclo)
• Grafos con herencia de distancias (las distancias entre vértices de un subgrafo inducido son las mismas que en el grafo original)
• Grafos de permutaciones
• Grafos de comparabilidad (un vértice por cada elemento en un orden parcial, una arista entre cada par de elementos comparables)
• Grafos Rueda con una cantidad impar de vértices

• Grafos perfectamente ordenables (grafos que pueden ser ordenados de tal forma que una coloración voraz es óptima para cada subgrafo inducido)
• Grafos de Meyniel (cada ciclo de largo impar mayor o igual a 5 tiene al menos 2 cuerdas)
• Grafos trivialmente perfectos (en cada subgrafo inducido el tamaño del mayor conjunto independiente es igual al número de cliques maximales)
• Grafos fuertemente perfectos (cada subgrafo inducido tiene un conjunto independiente que interseca todos sus cliques maximales)
• Grafos muy fuertemente perfectos (en cada subgrafo inducido, cada vértice pertenece a un conjunto independiente llegando a todos los cliques maximales)

Caracterización y teoremas de grafos perfectos

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 grafo es perfecto si y sólo si su complemento es también perfecto.

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)

Un grafo es perfecto si y sólo si es un grafo de Berge.

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 polinomial fue descubierto poco después por Chudnovsky, Cornuéjols, Liu, Seymour, and Vušković, sin utilizar el teorema de los grafos perfectos.

Referencias

• 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:  pp. 114. 
• Chudnovsky, Maria; Cornuéjols, Gérard; Liu, Xinming; Seymour, Paul; Vušković, Kristina (2005). «Recognizing Berge graphs». Combinatorica 25:  pp. 143–186. doi:10.1007/s00493-005-0012-8. 
• Chudnovsky, Maria; Robertson, Neil; Seymour, Paul; Thomas, Robin (2006). «The strong perfect graph theorem». Annals of Mathematics 164 (1):  pp. 51–229. http://annals.princeton.edu/annals/2006/164-1/p02.xhtml. 
• Gallai, Tibor (1958). «Maximum-minimum Sätze über Graphen». Acta Math. Acad. Sci. Hungar. 9:  pp. 395–434. doi:10.1007/BF02020271. 
• Golumbic, Martin Charles (1980), Algorithmic Graph Theory and Perfect Graphs, Academic Press, ISBN 0-444-51530-5, http://www.elsevier.com/wps/find/bookdescription.cws_home/699916/description#description 
• Grötschel, Martin; Lovász, László; Schrijver, Alexander (1988), Geometric Algorithms and Combinatorial Optimization, Springer-Verlag 
• Lovász, László (1972). «Normal hypergraphs and the perfect graph conjecture». Discrete Mathematics 2:  pp. 253–267. doi:10.1016/0012-365X(72)90006-4. 
• Lovász, László (1972). «A characterization of perfect graphs». Journal of Combinatorial Theory, Series B 13:  pp. 95–98. doi:10.1016/0095-8956(72)90045-7.