ein Graph G mit der Eigenschaft χ(H) = ω(H) für jeden induzierten Teilgraphen H von G, wobei χ(H) die chromatische Zahl und ω(H) die Cliquenzahl von H bedeuten.

Damit ist also ein Graph G perfekt, wenn für jeden induzierten Teilgraphen H von G die chromatische Zahl χ(H) die triviale untere Schranke ω(H) annimmt. Aus der Identität β(B) = α₀(B) von König für bipartite Graphen B, wobei β(B) die Eckenüberdeckungszahl und α₀(B) die Matching- zahl von B bedeuten, folgt, daß die bipartiten Graphen perfekt sind. Schwieriger ist der Nachweis der Tatsache, daß auch die chordalen Graphen perfekt sind, welche auf A. Hajnál und J. Surányi (1958) zurückgeht.

Das Konzept der perfekten Graphen wurde 1960 von C. Berge entwickelt, der gleichzeitig die Vermutung aussprach, daß ein Graph G genau dann perfekt ist, wenn auch sein Komplementärgraph G diese Eigenschaft besitzt. Berges Vermutung wurde dann 1972 durch L. Lovász tatsächlich bestätigt.

Ein Graph G ist genau dann perfekt, wenn \(\bar{G}\)perfekt ist.

Dieses Resultat von Lovász zählt zu den Hauptergebnissen der Theorie der perfekten Graphen und wird heute perfekte-Graphen-Satz oder perfect graph theorem genannt. Ist α(G) die Unabhängigkeitszahl und Θ(G) die Cliquenüberdeckungszahl von G, so erhält man sofort die beiden Identitäten \begin{eqnarray}\alpha (G)=\omega (\bar{G})\,\,\,\,\text{und}\,\,\,\,{\rm{\Theta }}(G)=\chi (\bar{G}).\end{eqnarray}

Daher ergibt sich unmittelbar aus dem perfekte- Graphen-Satz, daß ein Graph G genau dann perfekt ist, wenn Θ(H) = α(H) für jeden induzierten Teilgraphen H von G gilt.

Ein älteres Ergebnis von R.P. Dilworth aus dem Jahre 1950 besagt, daß auch die transitiv orientierbaren Graphen perfekt sind. Dabei heißt ein Graph G transitiv orientierbar, falls G eine Orientierung D besitzt, die die folgende Bedingung erfüllt: Gehören die beiden Bogen (u, v) und (v, w) zu dem gerichteten Graphen D, so auch der Bogen (u, w).

Ein Kreis ungerader Länge ≥ 5 ist sicher nicht perfekt, womit alle Graphen, die einen Kreis ungerader Länge ≥ 5 als induzierten Teilgraphen enthalten, ebenfalls nicht perfekt sind. Nach dem perfekte-Graphen-Satz von Lovász ist aber ein Graph G auch dann nicht perfekt, wenn \(\bar{G}\) einen Kreis ungerader Länge ≥ 5 als induzierten Teilgraphen besitzt. Bis heute ungelöst ist die Umkehrung dieser Aussage, die 1960 von C. Berge vermutet wurde und in der Literatur als perfekte-Graphen- Vermutung oder strong perfect graph conjecture bekannt ist:

Ein Graph G ist genau dann perfekt, wenn weder G noch \(\bar{G}\)einen Kreis ungerader Länge ≥ 5 als induzierten Teilgraphen enthält.

Nur für einige Spezialklassen, wie z. B. den planaren Graphen (A. Tucker 1973), ist diese Vermutung bewiesen worden.

Die Bestimmung der Parameter χ(G), ω(G), Θ(G) sowie α(G) führt bei beliebigen Graphen zu NP- schweren Problemen. Dagegen haben 1981 M. Grötschel, L. Lovász und A. Schrijver gezeigt, daß man alle diese Größen für perfekte Graphen in polynomialer Zeit berechnen kann. Somit sind die perfekten Graphen auch vom algorithmischen Standpunkt interessant.

[1] Brandstädt, A.; Le, V.B.; Spinrad, J.P.: Graph Classes: A Survey. Monographs on Discrete Mathematics and Applications 3, SIAM, 1999.
[2] Golumbic, M.C.: Algorithmic Graph Theory and Perfect Graphs. Academic Press, London, New York, San Francisco, 1980.
[3] Simon, K: Effiziente Algorithmen für perfekte Graphen. Teubner, Stuttgart, 1992.