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
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
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
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
- weakly chordal – Eintrag im Information System on Graph Classes and their Inclusions
Einzelnachweise
- ↑ 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.
