Perfekter Graph

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche
perfekter Graph
Beispiele:
Paley9-perfect.svg

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,[1] deren Berechnung auf allgemeinen Graphen NP-vollständig ist. Es kann in polynomieller Zeit bestimmt werden, ob ein Graph perfekt ist.[2] 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:

  1. G ist ein perfekter Graph
  2. Das Komplement von G ist perfekt.
  3. G enthält weder einen ungeraden Kreis der Länge mindestens 5 noch das Komplement eines solchen Kreises als induzierten Subgraphen.
    Graphen mit dieser Eigenschaft heißen Berge Graphen oder schwach chordal.

Die zweite Charakteristik ist als schwacher Satz über perfekte Graphen bekannt, wurde schon 1972 von László Lovász bewiesen und wird deshalb nun Satz von Lovász genannt. Die dritte Charakteristik ist auch als starker Satz über perfekte Graphen bekannt und wurde erst im Mai 2002 bewiesen.[3] Beide Aussagen wurden schon 1960 von Claude Berge als Vermutung aufgestellt (auf einer Konferenz in Halle-Wittenberg, veröffentlicht wurde seine Vermutung erst 1963).

Literatur[Bearbeiten]

Einzelnachweise[Bearbeiten]

  1. Grötschel, Lovász, Alexander Schrijver: Geometric Algorithms and Combinatorial Optimization. Springer-Verlag, 1988, Kapitel 9, Stable Sets in Graphs, S. 273–303
  2. Chudnovsky, Cornuéjols, Liu, Seymour, Vušković: Recognizing Berge Graphs. In: Combinatorica, Bd. 25, Nr. 2, 2005, S. 143–186
  3. Chudnovsky, Robertson, Seymour, Thomas: The strong perfect graph theorem. In: Annals of Mathematics, Bd. 164, 2006, S. 51–229