Saturday, May 30, 2015

Weakly chordal graphs

The weakly chordal graphs are a subclass of the perfect graphs that exclude all holes and antiholes. The weakly chordal graphs are an important class of graphs in order theory. Well the class of weakly chordal graphs does not include all comparability graphs or all cocomparability graphs it does include all permutation graphs which are the graphs that are both comparability and cocomparability. This means it also includes the cographs which also happen to be permutation graphs.

The chordal graphs as well as their complements the cochordal graphs are weakly chordal. The trivially perfect graphs are precisely those graphs that are both chordal and cographs. The cotrivially perfect graphs are precisely those graphs that are both cochordal and cographs. The trivially perfect graphs and the cotrivially perfect graphs can both be expressed entirely in terms of preorders. Only weakly chordal graphs can be described entirely in terms of preorders in this sense.