Weak chordal graph

In the graph theory is a graph weakly chordal (English weakly chordal ) if neither the graph nor his complement graph induced circuits with more than 4 nodes. ${\ displaystyle G}$ ${\ displaystyle G}$ ${\ displaystyle {\ bar {G}}}$

Alternative characterization

A 2-pair of nodes of a graph are nodes x, y so that all induced paths of between x and y have exactly 2 edges.

A graph is weakly chordal if and only if every connected induced subgraph either contains a 2-pair or is a complete graph .

properties

The set of weakly chordal graphs is closed with complement formation. The complement of a weakly chordal graph is itself a weakly chordal graph.

Relationships to other graph classes

All weakly chordal graphs are perfect graphs .

Subclasses of weakly chordal graphs are chordal graphs and chordal bipartite graphs . Whereby chordal bipartite graphs are not a subclass of the chordal graphs.

Web links

weakly chordal - Entry in the Information System on Graph Classes and their Inclusions

Individual evidence

^ ^A ^b Ryan B. Hayward: Weakly triangulated graphs . In: J. Comb. Theory (B) . tape 39 , 1985, pp. 200--208 , doi : 10.1016 / 0095-8956 (85) 90050-4 .
↑ Ryan Hayward, Chinh Hoàng, Frédéric Maffray: Optimizing weakly triangulated graphs . In: Graphs and Combinatorics . tape 5 , p. 339-349 , doi : 10.1007 / BF01788689 .

[Hayward1985-1] A ^b Ryan B. Hayward: Weakly triangulated graphs . In: J. Comb. Theory (B) . tape 39 , 1985, pp. 200--208 , doi : 10.1016 / 0095-8956 (85) 90050-4 .

[2] Ryan Hayward, Chinh Hoàng, Frédéric Maffray: Optimizing weakly triangulated graphs . In: Graphs and Combinatorics . tape 5 , p. 339-349 , doi : 10.1007 / BF01788689 .