of its induced subgraphs the clique cover number equals the number of maximal cliques. They are the graphs with the property that in each of its induced subgraphs the clique number equals the pseudo-Grundy number. They are the graphs with the property that in each of its induced subgraphs the chromatic number equals the pseudo-Grundy number. 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, a Ptolemaic 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). Windmill graphs are trivially perfect. Recognition describes a simple linear time algorithm for recognizing trivially perfect graphs, based on lexicographic breadth-first search. Whenever the LexBFS algorithm removes a vertex from the first set on its queue, the algorithm checks that all remaining neighbors of belong to the same set; if not, one of the forbidden induced subgraphs can be constructed from . If this check succeeds for every , 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. Determining if a general graph is edge deletions away from a trivially perfect graph is NP-complete, fixed-parameter tractable and can be solved in time. Notes References . . . . . . . . . . . External links Graph families Perfect graphs