Chordal bipartiter Graph

In der Graphentheorie heißt ein endlicher Graph G chordal bipartit (englisch chordal bipartite), falls jeder induzierte Kreis in G genau die Länge 4 hat. Auf dieser Graphenklasse lassen sich einige NP-schwere Probleme effizient lösen.

Definitionen

Ein bipartiter Graph $G=(V,E)$ mit bipartiter Zerlegung $V=A\cup B$ heißt chordal bipartit, wenn er eine (und damit alle) der folgenden äquivalenten Definitionen erfüllt:

• jeder Kreis der Länge mindestens 6 hat eine Sehne (englisch: "chord"), d. h. es gibt im Graphen eine Kante zwischen zwei im Kreis nicht benachbarten Knoten.
• der aus $G$ durch Hinzufügen aller Kanten zwischen Knoten in $A$ entstehende Graph ist stark chordal.
• es existiert eine Anordnung der Kanten, so dass (für die durch $G_{0}=G,G_{i}=G_{i-1}-e_{i}$ definierte Folge) die Vereinigung der Nachbarschaften der beiden Knoten von $e_{i}=\left\{x_{i},y_{i}\right\}$ ein vollständig bipartiter Teilgraph in $G_{i-1}$ ist, d. h. jeder Knoten in $N(x_{i})$ ist mit jedem Knoten in $N(y_{i})$ durch eine Kante in $G_{i-1}$ verbunden.

Man beachte, dass chordal bipartite Graphen nicht chordal sein müssen. Genauer wäre eigentlich die Bezeichnung schwach chordal bipartit, da diese Graphen schwach chordal und bipartit sind, andererseits sind Verwechslungen nicht zu befürchten, da Kreise in bipartiten Graphen stets eine gerade Länge haben müssen.

Ein Graph ist genau dann stark chordal, wenn sein assoziierter bipartiter Graph chordal bipartit ist.

Literatur

• Mihály Bakonyi, Aaron Bono: Several Results on Chordal Bipartite Graphs. Czechoslovak Mathematical Journal, Volume 47 - Number 4 - Dezember 1997, ISSN 0011-4642, S. 577–583 PDF
• Brandstädt, Andreas; Le, Van Bang; Spinrad, Jeremy (1999), Graph Classes: A Survey, SIAM Monographs on Discrete Mathematics and Applications, ISBN 0-89871-432-X.
• Jorge L. Ramírez Alfonsín, Bruce A. Reed: Perfect Graphs. Wiley 2001, ISBN 9780471489702, S. 141 (eingeschränkte Online-Version in der Google-Buchsuche-USA)
• Golumbic, Martin Charles; Goss, Clinton F.: Perfect elimination and chordal bipartite graphs. J. Graph Theory 2 (1978), no. 2, 155–163. PDF

Weblinks

• chordal bipartite - Eintrag im Information System on Graph Classes and their Inclusions