Perfekter Graph
In der Graphentheorie heisst ein Graph perfekt wenn für jeden indizierten Subgraphen gilt, dass seine Cliquenzahl mit seiner chromatische 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 geniessen!)
Beispiele für perfekte Graphen sind bipartite Graphen, Linegraphen und die Komplemente dieser. 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 Grapen sind triangulierte Graphen.
Nach dem perfekten Graphen Satz 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 perfekter Graphen Satz bekannt und wurde schon 1972 bewiesen. Die dritte Charakteristik ist auch als starker perfekter Graphen Satz bekannt und wurde erst im Mai 2002 bewiesen. Beide Aussagen wurden schon 1961 von C. Berge als Vermutung aufgestellt.
Literatur
- Perfect Problems Internetseite von Vašek Chvátal über Perfekte Graphen.