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 einen Graphen mit Knotenmenge und Kantenmenge , einen von induzierten Teilgraphen, die chromatische Zahl, die Cliquenzahl, die Stabilitätszahl und die Cliquenüberdeckungszahl (also die kleinste natürliche Zahl , sodass in Cliquen partitioniert werden kann).
Die folgenden Bedingungen sind dann (formal) äquivalent:
für alle (G ist perfekt). für alle (Gc ist perfekt). für alle .
Literatur Reinhard Diestel: Graphentheorie. Springer 2006, ISBN 3-540-21391-0, Satz 4.5.4
Weblinks
Perfekte-Graphen-Satz, schwacher