Trivially perfect graph

Construction of a trivially perfect graph from nested intervals and from the reachability relationship in a tree

In graph theory, a trivially perfect graph is a graph with the property that in each of its induced subgraphs the size of the maximum independent set equals the number of maximal cliques.[1] Trivially perfect graphs were first studied by (Wolk 1962, 1965) but were named by Golumbic (1978); Golumbic writes that "the name was chosen since it is trivial to show that such a graph is perfect." Trivially perfect graphs are also known as comparability graphs of trees,[2] arborescent comparability graphs,[3] and quasi-threshold graphs.[4]

Equivalent characterizations

Trivially perfect graphs have several other equivalent characterizations:

Related classes of graphs

It follows from the equivalent characterizations of trivially perfect graphs that every trivially perfect graph is also a cograph, a chordal graph, an interval graph, and a perfect graph.

The threshold graphs are exactly the graphs that are both themselves trivially perfect and the complements of trivially perfect graphs (co-trivially perfect graphs).[13]

Windmill graphs are trivially perfect.

Recognition

Chu (2008) describes a simple linear time algorithm for recognizing trivially perfect graphs, based on lexicographic breadth-first search. Whenever the LexBFS algorithm removes a vertex v from the first set on its queue, the algorithm checks that all remaining neighbors of v belong to the same set; if not, one of the forbidden induced subgraphs can be constructed from v. If this check succeeds for every v, then the graph is trivially perfect. The algorithm can also be modified to test whether a graph is the complement graph of a trivially perfect graph, in linear time.

Notes

References

External links

This article is issued from Wikipedia - version of the Monday, February 08, 2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.