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.
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 .