grafo perfetto

Nella teoria dei grafi, un grafo perfetto è un grafo nel quale il numero cromatico di ogni sottografo indotto è uguale alla dimensione della cricca più grande di quel sottografo. Grazie al , sappiamo dal 2002 che i grafi perfetti sono la stessa cosa dei grafi di Berge. Un grafo G è un grafo di Berge se né G né il suo complemento hanno un di lunghezza dispari uguale a 5 o superiore. I grafi perfetti comprendono molte importanti famiglie di grafi, e servono a unificare risultati che collegano le colorazioni e le cricche in quelle famiglie. Per esempio, in tutti i grafi perfetti, il problema della colorazione dei grafi, il problema della cricca massima e il problema del massimo insieme indipendente possono essere tutti risolti in tempo polinomiale. In aggiunta, parecchi importanti teoremi di minimo e massimo in combinatoria, come il , possono essere espressi in termini della perfezione di certi grafi associati. La teoria dei grafi perfetti si sviluppò da un risultato del 1958 di Tibor Gallai che in linguaggio moderno può essere interpretato affermando che il complemento di un grafo bipartito è perfetto; questo risultato può anche essere visto come un semplice equivalente del , un risultato molto anteriore che collega gli accoppiamenti e le coperture dei vertici nei grafi bipartiti. Il primo uso della locuzione "grafo perfetto" pare che sia in un saggio del 1963 di , dal quale prendono nome i grafi di Berge. In questo saggio egli unificò il risultato di Gallai con vari risultati simili definendo i grafi perfetti, e congetturò l'equivalenza delle definizioni di grafo perfetto e di grafo di Berge; la congettura di Berge fu dimostrata nel 2002 come il .