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 für einen Graphen G V seine Eckenmenge, G_A einen von $A\subset V$ induzierter Teilgraphen, χ(G) die chromatische Zahl, ω(G) die Cliquenzahl, α(G) die Stabilitätszahl und die k(G) Zusammenhangszahl.

Die folgenden Bedingungen sind dann (formal) äquivalent:

1. χ(G_A) = ω(G_A) für alle $A \subseteq V$ (G perfekt).
2. k(G_A) = α(G_A) für alle $A \subseteq V$ (G^c perfekt).
3. $\alpha(G_A) \omega(G_A) \ge |A|$ für alle $A \subseteq V$.

Siehe auch: starker Perfekte-Graphen-Satz

Literatur

• Reinhard Diestel: Graphentheorie. Springer 2006, ISBN 3-540-21391-0, Satz 4.5.4 (elektronische Online-Version)

Weblinks

• Eric W. Weisstein: perfect graph theorem. In: MathWorld. (englisch)