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. Vorlage:Zitat

Im Folgenden bezeichne für einen Graphen G $V$ seine Eckenmenge, $G_A$ einen von $A\subset V$ induzierter Teilgraphen, $\chi (G)$ die chromatische Zahl, $\omega (G)$ die Cliquenzahl, $\alpha (G)$ die Stabilitätszahl und die $k(G)$ Zusammenhangszahl.

Die folgenden Bedingungen sind dann (formal) äquivalent:

1. $\chi (G_A)=\omega (G_A)$ für alle $A\subseteq V$ (G perfekt).
2. $k(G_A)=\alpha (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$.

Literatur

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

Weblinks

• Vorlage:MathWorld