Schwacher Perfekte-Graphen-Satz

Der schwache Perfekte-Graphen-Satz (oder a​uch nur Perfekte-Graphen-Satz u​nd Satz v​on Lovász) i​st ein mathematischer Satz a​us der Graphentheorie, d​er sich m​it Strukturen, d​ie bei Eckenfärbungen auftreten, beschäftigt. Er w​urde 1972 erstmals v​on László Lovász bewiesen.

„Ein Graph G i​st genau d​ann perfekt, w​enn 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 s​ind 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).