Schwach chordaler Graph
In der Graphentheorie heißt ein Graph schwach chordal (englisch weakly chordal), falls weder der Graph noch sein Komplementgraph induzierte Kreise mit mehr als 4 Knoten haben.[1]
Alternative Charakterisierung
[Bearbeiten | Quelltext bearbeiten]Ein 2-Paar von Knoten eines Graph sind Knoten x,y, sodass alle induzierten Pfade von zwischen x und y genau 2 Kanten haben.
Ein Graph ist schwach chordal genau dann wenn jeder zusammenhängender induzierter Teilgraph entweder ein 2-Paar enthält oder ein vollständiger Graph ist.[2]
Eigenschaften
[Bearbeiten | Quelltext bearbeiten]Die Menge der schwach chordalen Graphen ist unter Komplementbildung abgeschlossen. Das Komplement eines schwach chordalen Graphen ist selbst ein schwach chordaler Graph.
Beziehungen zu anderen Graphklassen
[Bearbeiten | Quelltext bearbeiten]Alle schwach chordalen Graphen sind perfekte Graphen.[1]
Unterklassen der schwach chordalen Graphen sind chordale Graphen und chordal bipartiten Graphen, wobei chordal bipartite Graphen keine Unterklasse der chordalen Graphen sind.
Weblinks
[Bearbeiten | Quelltext bearbeiten]- weakly chordal – Eintrag im Information System on Graph Classes and their Inclusions
Einzelnachweise
[Bearbeiten | Quelltext bearbeiten]- ↑ a b Ryan B. Hayward: Weakly triangulated graphs. In: J. Comb. Theory (B). Band 39, 1985, S. 200--208, doi:10.1016/0095-8956(85)90050-4.
- ↑ Ryan Hayward, Chính Hoàng, Frédéric Maffray: Optimizing weakly triangulated graphs. In: Graphs and Combinatorics. Band 5, S. 339–349, doi:10.1007/BF01788689.