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 ${\displaystyle V}$ seine Eckenmenge, ${\displaystyle G_{A}}$ einen von ${\displaystyle A\subset V}$ induzierter Teilgraphen, ${\displaystyle \chi (G)}$ die chromatische Zahl, ${\displaystyle \omega (G)}$ die Cliquenzahl, ${\displaystyle \alpha (G)}$ die Stabilitätszahl und die ${\displaystyle k(G)}$ Zusammenhangszahl.

Die folgenden Bedingungen sind dann (formal) äquivalent:

1. ${\displaystyle \chi (G_{A})=\omega (G_{A})}$ für alle ${\displaystyle A\subseteq V}$ (G perfekt).
2. ${\displaystyle k(G_{A})=\alpha (G_{A})}$ für alle ${\displaystyle A\subseteq V}$ (G^c perfekt).
3. ${\displaystyle \alpha (G_{A})\omega (G_{A})\geq |A|}$ für alle ${\displaystyle A\subseteq V}$.

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).