Trivially perfect graph

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

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.

Determining if a general graph is k edge deletions away from a trivially perfect graph is NP-complete,[15] fixed-parameter tractable[16] and can be solved in O(2.45k(m + n)) time.