Schwacher Perfekte-Graphen-Satz

Der schwache Perfekte-Graphen-Satz (oder auch nur Perfekte-Graphen-Satz und Satz von Lovász) ist ein mathematischer Satz aus der Graphentheorie, der sich mit Strukturen, die bei Eckenfärbungen auftreten, beschäftigt. Er wurde 1972 erstmals von László Lovász bewiesen.

„Ein Graph G ist genau dann perfekt, wenn sein komplementärer Graph G^c perfekt ist.“

Im Folgenden bezeichne <math>G = (V,E)</math> einen Graphen mit Knotenmenge <math>V</math> und Kantenmenge <math>E</math>, <math> G_A</math> einen von <math> A\subset V</math> induzierten Teilgraphen, <math>\chi(G) </math> die chromatische Zahl, <math> \omega(G)</math> die Cliquenzahl, <math>\alpha(G) </math> die Stabilitätszahl und die <math>\theta(G) </math> Cliquenüberdeckungszahl (also die kleinste natürliche Zahl <math>n</math>, sodass <math>G</math> in <math>n</math> Cliquen partitioniert werden kann).

Die folgenden Bedingungen sind dann (formal) äquivalent:

1. <math>\chi(G_A) = \omega(G_A)</math> für alle <math>A \subseteq V</math> (G ist perfekt).
2. <math>\theta(G_A) = \alpha(G_A)</math> für alle <math>A \subseteq V</math> (G^c ist perfekt).
3. <math>\alpha(G_A) \omega(G_A) \ge |A|</math> für alle <math>A \subseteq V</math>.

Literatur

• Reinhard Diestel: Graphentheorie. Springer 2006, ISBN 3-540-21391-0, Satz 4.5.4

Weblinks

• Eric W. Weisstein: Perfect Graph Theorem. In: MathWorld (englisch).