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.

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}$.