Perfekter Graph
aus Wikipedia, der freien Enzyklopädie
In der Graphentheorie heißt ein Graph perfekt, wenn für jeden induzierten Subgraphen gilt, dass seine Cliquenzahl mit seiner chromatischen Zahl übereinstimmt. Ein induzierter Subgraph eines Graphen besteht dabei aus einer Teilmenge der Knoten und allen inzidenten Kanten.
In einem perfekten Graphen können chromatische Zahl, Cliquenzahl und Stabilitätszahl in polynomieller Zeit berechnet werden. Es kann in polynomieller Zeit bestimmt werden, ob ein Graph perfekt ist. (Erst seit Januar 2003 bekannt und wohl noch mit Vorsicht zu genießen!)
Beispiele für perfekte Graphen sind bipartite Graphen, Kantengraphen bipartiter Graphen und deren Komplemente. Sie bilden die Basis für den starken perfekten Graphensatz und werden daher in diesem Zusammenhang auch als einfache perfekte Graphen (englisch basic) bezeichnet. Weitere Beispiele für perfekte Graphen sind triangulierte Graphen und chordal bipartite Graphen.
Nach dem Satz über perfekte Graphen sind folgende Aussagen äquivalent:
- G ist ein perfekter Graph
- Das Komplement von G ist perfekt.
- G enthält weder einen ungeraden Kreis der Länge mindestens 5 noch das Komplement eines solchen Kreises als induzierten Subgraphen.
Die zweite Charakteristik ist als schwacher Satz über perfekte Graphen bekannt und wurde schon 1972 bewiesen. Die dritte Charakteristik ist auch als starker Satz über perfekte Graphen bekannt und wurde erst im Mai 2002 bewiesen. Beide Aussagen wurden schon 1961 von C. Berge als Vermutung aufgestellt.
siehe Satz von Lovász
[Bearbeiten] Literatur
- Perfect Problems Internetseite von Vašek Chvátal über Perfekte Graphen.
