Grafo perfecto

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.

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.

Un avance importante fue la respuesta afirmativa a la entonces conjetura 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.

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.