Schwach chordaler Graph

In der Graphentheorie heißt ein Graph $G$ schwach chordal (englisch weakly chordal), falls weder der Graph $G$ noch sein Komplementgraph ${\bar {G}}$ 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.

[Hayward1985-1] 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.

[2] 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.

[1]

[2]