Amongst the set of all graphs the perfect graphs are particularly interesting. Perfect graphs subsume both comparability graphs and co-comparability graphs so they can describe both the comparability and the incomparability conditions of partial ordering relations. As the the perfect graphs exclude odd holes and odd anti-holes they are far easier to describe using partial orders themselves.
The trivially perfect graphs and the co trivially perfect graphs are perfect graphs that are of particular interest to us. They can both be described entirely using preorders produced by the immediate reachability conditions on the graphs. Equivalence graphs are trivially perfect and their complements the complete partite graphs are co trivially perfect.
The threshold graphs are both trivially perfect and co trivially perfect. The threshold equivalence graphs form a Moore family of graphs with their own closure operation defined by split completion. Both empty graphs and complete graphs belong to the class of threshold equivalence graphs.
No comments:
Post a Comment