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 ob ein Graph perfekt ist.
Beispiele für perfekte Graphen sind bipartite Graphen und triangulierte Graphen.
Nach dem perfekten Graphen Satz sind folgende Aussagen äquivalent:
- G ist ein perfekter Graph
- G enthält weder einen ungeraden Kreis der Länge mindestens 5 noch das Komplement eines solchen Kreises als induzierten Subgraphen.
- Das Komplement von G ist perfekt
Letztere Characteristik ist auch als starker perfekter Graphen Satz bekannt und wurde erst 2002 bewiesen.
Literatur
- Perfect Problems Internetseite von Vašek Chvátal über Perfekte Graphen.