Colloquium - 16:00
Abstract: Wir fuehren ein Mass fuer die Imperfektheit eines Graphen ein, gegeben durch zwei Superklassen perfekter Graphen: rang-perfekte und schwach rang-perfekte Graphen. Dazu relaxieren wir den Perfektheitsbegriff bezueglich der polyedertheoretischen Charakterisierung perfekter Graphen ueber eine Beschreibung des Stabile-Mengen-Polytops. Das Stabile-Mengen- Polytop STAB(G) ist definiert als konvexe Huelle der Inzidenzvektoren aller stabilen Mengen von G. Das Polytop besitzt eine weitere Darstellung als Durchschnitt endlich vieler Halbraeume, das entsprechende System von Facetten ist jedoch fuer die meisten Graphen unbekannt. Cliquebedingungen x(Q) <= 1 mit Q subseteq G Clique sind fuer alle Graphen G gueltig und liefern nach Padberg (1973) Facetten von STAB(G), falls Q inklusions-maximale Clique ist. Perfekte Graphen sind dadurch charakterisiert, dass Nichtnegativitaets- und Cliquebedingungen die einzigen Facetten des Stabile-Mengen-Polytops sind. Nach Groetschel, Lovasz, und Schrijver (1988) ist ein Weg, den Perfektheitsbegriff zu relaxieren, Cliquebedingungen durch andere Ungleichungsklassen zu verallgemeinern und Graphen zu betrachten, deren Stabile-Mengen-Polytop durch Nichtnegativitaets- bedingungen und diese Ungleichungen gegeben ist. Eine natuerliche Verallgemeinerung von Cliquebedingungen sind sog. Rangbe- dingungen x(G') <= alpha(G') assoziiert mit Untergraphen G' von G (alpha(G') bezeichnet die Kardinalitaet einer groessten stabilen Menge von G'). Rangbedingungen sind offensichtlich gueltig und liefern fuer G' = G nach Padberg (1974) in einigen Faellen Facetten von STAB(G). Im Falle G' subset G koennen fuer diese Rangbedingungen durch Padbergs Liftingmethode fuer die Knoten in G - G' geeignete Koeffizienten bestimmt werden, so dass die gelifteten Rangbedingungen Facetten von STAB(G) ergeben. Wir definieren zwei Superklassen perfekter Graphen und nennen Graphen rang- perfekt, falls ihr Stabile-Mengen-Polytop durch Nichtnegativitaets- und Rangbedingungen beschrieben ist, und schwach rang-perfekt, falls dies fuer Nichtnegativitaets- und geliftete Rangbedingungen gilt. Wir geben einige bereits in der Literatur bekannte Beispiele fuer rang-perfekte und schwach rang-perfekte Graphen an und untersuchen fuer weitere Graphen, ob diese zu einer der beiden Klassen gehoeren.