# Trivially perfect graph

Last updated

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:

• They are the comparability graphs of order-theoretic trees. That is, let T be a partial order such that for each tT, the set {sT : s < t} is well-ordered by the relation <, and also T possesses a minimum element r. Then the comparability graph of T is trivially perfect, and every trivially perfect graph can be formed in this way. [5]
• They are the graphs that do not have a P4 path graph or a C4 cycle graph as induced subgraphs. [6]
• They are the graphs in which every connected induced subgraph contains a universal vertex. [7]
• They are the graphs that can be represented as the interval graphs for a set of nested intervals. A set of intervals is nested if, for every two intervals in the set, either the two are disjoint or one contains the other. [8]
• They are the graphs that are both chordal and cographs. [9] This follows from the characterization of chordal graphs as the graphs without induced cycles of length greater than three, and of cographs as the graphs without induced paths on four vertices (P4).
• They are the graphs that are both cographs and interval graphs. [9]
• They are the graphs that can be formed, starting from one-vertex graphs, by two operations: disjoint union of two smaller trivially perfect graphs, and the addition of a new vertex adjacent to all the vertices of a smaller trivially perfect graph. [10] These operations correspond, in the underlying forest, to forming a new forest by the disjoint union of two smaller forests and forming a tree by connecting a new root node to the roots of all the trees in a forest.
• They are the graphs in which, for every edge uv, the neighborhoods of u and v (including u and v themselves) are nested: one neighborhood must be a subset of the other. [11]
• They are the permutation graphs defined from stack-sortable permutations. [12]
• They are the graphs with the property that in each of its induced subgraphs the clique cover number equals the number of maximal cliques. [13]
• They are the graphs with the property that in each of its induced subgraphs the clique number equals the pseudo-Grundy number. [13]
• They are the graphs with the property that in each of its induced subgraphs the chromatic number equals the pseudo-Grundy number. [13]

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). [14]

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.

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. [17]

## Notes

1. Brandstädt, Le & Spinrad (1999), definition 2.6.2, p.34; Golumbic (1978).
2. Brandstädt, Le & Spinrad (1999), theorem 6.6.1, p. 99; Golumbic (1978), corollary 4.
3. Brandstädt, Le & Spinrad (1999), theorem 6.6.1, p. 99; Golumbic (1978), theorem 2. Wolk (1962) and Wolk (1965) proved this for comparability graphs of rooted forests.
4. Brandstädt, Le & Spinrad (1999), p. 51.
5. Brandstädt, Le & Spinrad (1999), p. 248; Yan, Chen & Chang (1996), theorem 3.
6. Yan, Chen & Chang (1996), theorem 3.
7. Brandstädt, Le & Spinrad (1999), theorem 6.6.3, p. 100; Golumbic (1978), corollary 5.

## Related Research Articles

In graph theory, an interval graph is an undirected graph formed from a set of intervals on the real line, with a vertex for each interval and an edge between vertices whose intervals intersect. It is the intersection graph of the intervals.

In graph theory, a perfect graph is a graph in which the chromatic number of every induced subgraph equals the size of the largest clique of that subgraph. Equivalently stated in symbolic terms an arbitrary graph is perfect if and only if we have:

In graph theory, the perfect graph theorem of László Lovász states that an undirected graph is perfect if and only if its complement graph is also perfect. This result had been conjectured by Berge, and it is sometimes called the weak perfect graph theorem to distinguish it from the strong perfect graph theorem characterizing perfect graphs by their forbidden induced subgraphs.

In the mathematical area of graph theory, a chordal graph is one in which all cycles of four or more vertices have a chord, which is an edge that is not part of the cycle but connects two vertices of the cycle. Equivalently, every induced cycle in the graph should have exactly three vertices. The chordal graphs may also be characterized as the graphs that have perfect elimination orderings, as the graphs in which each minimal separator is a clique, and as the intersection graphs of subtrees of a tree. They are sometimes also called rigid circuit graphs or triangulated graphs.

In graph theory, the complement or inverse of a graph G is a graph H on the same vertices such that two distinct vertices of H are adjacent if and only if they are not adjacent in G. That is, to generate the complement of a graph, one fills in all the missing edges required to form a complete graph, and removes all the edges that were previously there. It is not, however, the set complement of the graph; only the edges are complemented.

In graph theory, a cograph, or complement-reducible graph, or P4-free graph, is a graph that can be generated from the single-vertex graph K1 by complementation and disjoint union. That is, the family of cographs is the smallest class of graphs that includes K1 and is closed under complementation and disjoint union.

In graph theory, a comparability graph is an undirected graph that connects pairs of elements that are comparable to each other in a partial order. Comparability graphs have also been called transitively orientable graphs, partially orderable graphs, containment graphs, and divisor graphs. An incomparability graph is an undirected graph that connects pairs of elements that are not comparable to each other in a partial order.

In graph theory, a branch of mathematics, a split graph is a graph in which the vertices can be partitioned into a clique and an independent set. Split graphs were first studied by Földes and Hammer, and independently introduced by Tyshkevich and Chernyak (1979).

In graph theory, a threshold graph is a graph that can be constructed from a one-vertex graph by repeated applications of the following two operations:

1. Addition of a single isolated vertex to the graph.
2. Addition of a single dominating vertex to the graph, i.e. a single vertex that is connected to all other vertices.

In graph theory, the clique-width of a graph is a parameter that describes the structural complexity of the graph; it is closely related to treewidth, but unlike treewidth it can be bounded even for dense graphs. It is defined as the minimum number of labels needed to construct by means of the following 4 operations :

1. Creation of a new vertex v with label i
2. Disjoint union of two labeled graphs G and H
3. Joining by an edge every vertex labeled i to every vertex labeled j, where
4. Renaming label i to label j

In graph theory, a branch of discrete mathematics, a distance-hereditary graph is a graph in which the distances in any connected induced subgraph are the same as they are in the original graph. Thus, any induced subgraph inherits the distances of the larger graph.

In mathematics, a permutation graph is a graph whose vertices represent the elements of a permutation, and whose edges represent pairs of elements that are reversed by the permutation. Permutation graphs may also be defined geometrically, as the intersection graphs of line segments whose endpoints lie on two parallel lines. Different permutations may give rise to the same permutation graph; a given graph has a unique representation if it is prime with respect to the modular decomposition.

In graph theory, a perfectly orderable graph is a graph whose vertices can be ordered in such a way that a greedy coloring algorithm with that ordering optimally colors every induced subgraph of the given graph. Perfectly orderable graphs form a special case of the perfect graphs, and they include the chordal graphs, comparability graphs, and distance-hereditary graphs. However, testing whether a graph is perfectly orderable is NP-complete.

In computer science, lexicographic breadth-first search or Lex-BFS is a linear time algorithm for ordering the vertices of a graph. The algorithm is different from a breadth-first search, but it produces an ordering that is consistent with breadth-first search.

In the mathematical area of graph theory, an undirected graph G is strongly chordal if it is a chordal graph and every cycle of even length in G has an odd chord, i.e., an edge that connects two vertices that are an odd distance (>1) apart from each other in the cycle.

In graph theory, a branch of mathematics, an indifference graph is an undirected graph constructed by assigning a real number to each vertex and connecting two vertices by an edge when their numbers are within one unit of each other. Indifference graphs are also the intersection graphs of sets of unit intervals, or of properly nested intervals. Based on these two types of interval representations, these graphs are also called unit interval graphs or proper interval graphs; they form a subclass of the interval graphs.

In the mathematical area of graph theory, a chordal bipartite graph is a bipartite graph B = (X,Y,E) in which every cycle of length at least 6 in B has a chord, i.e., an edge that connects two vertices that are a distance > 1 apart from each other in the cycle. A better name would be weakly chordal and bipartite since chordal bipartite graphs are in general not chordal as the induced cycle of length 4 shows.

In the mathematical area of graph theory, an undirected graph G is dually chordal if the hypergraph of its maximal cliques is a hypertree. The name comes from the fact that a graph is chordal if and only if the hypergraph of its maximal cliques is the dual of a hypertree. Originally, these graphs were defined by maximum neighborhood orderings and have a variety of different characterizations. Unlike for chordal graphs, the property of being dually chordal is not hereditary, i.e., induced subgraphs of a dually chordal graph are not necessarily dually chordal, and a dually chordal graph is in general not a perfect graph. Dually chordal graphs appeared first under the name HT-graphs.

In the mathematical area of graph theory, a k-leaf power of a tree is a graph whose vertices are the leaves of and whose edges connect pairs of leaves whose distance in is at most . That is, is an induced subgraph of the graph power , induced by the leaves of . For a graph constructed in this way, is called a k-leaf root of .

In graph theory, a universal vertex is a vertex of an undirected graph that is adjacent to all other vertices of the graph. It may also be called a dominating vertex, as it forms a one-element dominating set in the graph.

## References

• Brandstädt, Andreas; Le, Van Bang; Spinrad, Jeremy (1999), , SIAM Monographs on Discrete Mathematics and Applications, ISBN   0-89871-432-X .
• Cai, L. (1996), "Fixed-parameter tractability of graph modification problems for hereditary properties", Information Processing Letters , 58 (4): 171–176, doi:10.1016/0020-0190(96)00050-6 .
• Chu, Frank Pok Man (2008), "A simple linear time certifying LBFS-based algorithm for recognizing trivially perfect graphs and their complements", Information Processing Letters , 107 (1): 7–12, doi:10.1016/j.ipl.2007.12.009 .
• Donnelly, Sam; Isaak, Garth (1999), "Hamiltonian powers in threshold and arborescent comparability graphs", Discrete Mathematics , 202 (1–3): 33–44, doi:
• Golumbic, Martin Charles (1978), "Trivially perfect graphs", Discrete Mathematics , 24 (1): 105–107, doi:.
• Gurski, Frank (2006), "Characterizations for co-graphs defined by restricted NLC-width or clique-width operations", Discrete Mathematics , 306 (2): 271–277, doi:.
• Nastos, James; Gao, Yong (2010), "A Novel Branching Strategy for Parameterized Graph Modification Problems", Lecture Notes in Computer Science, 6509: 332–346, arXiv:.
• Rotem, D. (1981), "Stack sortable permutations", Discrete Mathematics , 33 (2): 185–196, doi:, MR   0599081 .
• Rubio-Montiel, C. (2015), "A new characterization of trivially perfect graphs", Electronic Journal of Graph Theory and Applications, 3 (1): 22–26, doi:.
• Sharan, Roded (2002), "Graph modification problems and their applications to genomic research", PhD Thesis, Tel Aviv University.
• Wolk, E. S. (1962), "The comparability graph of a tree", Proceedings of the American Mathematical Society (5 ed.), 13: 789–795, doi:.
• Wolk, E. S. (1965), "A note on the comparability graph of a tree", Proceedings of the American Mathematical Society (1 ed.), 16: 17–20, doi:.
• Yan, Jing-Ho; Chen, Jer-Jeong; Chang, Gerard J. (1996), "Quasi-threshold graphs", Discrete Applied Mathematics , 69 (3): 247–255, doi:.