In graph theory

Graph theory

In mathematics and computer science, graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects from a certain collection. A "graph" in this context refers to a collection of vertices or 'nodes' and a collection of edges that connect pairs of...

, 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. Trivially perfect graphs were first studied by but were named by ; Golumbic writes that "the name was chosen since it is trivial to show that such a graph is perfect

Perfect graph

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

." Trivially perfect graphs are also known as comparability graphs of trees, arborescent comparability graphs, and quasi-threshold graphs.

Equivalent characterizations

Trivially perfect graphs have several other equivalent characterizations:

• They are the comparability graph
  Comparability graph
  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...
  
  s of rooted forests. That is, if P is the partial order formed by the reachability
  Reachability
  In graph theory, reachability is the notion of being able to get from one vertex in a directed graph to some other vertex. Note that reachability in undirected graphs is trivial — it is sufficient to find the connected components in the graph, which can be done in linear time.- Definition :For a...
  
   relationship between vertices in a rooted forest, then the comparability graph of P is trivially perfect, and every trivially perfect graph can be formed in this way.
• They are the graphs that do not have a three-edge path graph
  Path graph
  In the mathematical field of graph theory, a path graph or linear graph is a particularly simple example of a tree, namely a tree with two or more vertices that is not branched at all, that is, contains only vertices of degree 2 and 1...
  
   or a four-edge cycle graph
  Cycle graph
  In graph theory, a cycle graph or circular graph is a graph that consists of a single cycle, or in other words, some number of vertices connected in a closed chain. The cycle graph with n vertices is called Cn...
  
   as induced subgraphs.
• They are the graphs that can be represented as the interval graph
  Interval graph
  In graph theory, an interval graph is the intersection graph of a multiset of intervals on the real line. It has one vertex for each interval in the set, and an edge between every pair of vertices corresponding to intervals that intersect.-Definition:...
  
  s for a set of nested intervals
  Interval (mathematics)
  In mathematics, a interval is a set of real numbers with the property that any number that lies between two numbers in the set is also included in the set. For example, the set of all numbers satisfying is an interval which contains and , as well as all numbers between them...
  
  . A set of intervals is nested if, for every two intervals in the set, either the two are disjoint or one contains the other.
• They are the graphs that are both chordal
  Chordal graph
  In the mathematical area of graph theory, a graph is chordal if each of its cycles of four or more nodes has a chord, which is an edge joining two nodes that are not adjacent in the cycle. An equivalent definition is that any chordless cycles have at most three nodes...
  
   and cograph
  Cograph
  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...
  
  s. 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 path
  Induced path
  In the mathematical area of graph theory, an induced path in an undirected graph G is a path that is an induced subgraph of G. That is, it is a sequence of vertices in G such that each two adjacent vertices in the sequence are connected by an edge in G, and each two nonadjacent vertices in the...
  
  s of length three.
• They are the graphs that are both cographs and interval graphs.
• 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. 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.

Related classes of graphs

It follows from the equivalent characterizations of trivially perfect graphs that every trivially perfect graph is also a cograph

Cograph

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

, a chordal graph

Chordal graph

In the mathematical area of graph theory, a graph is chordal if each of its cycles of four or more nodes has a chord, which is an edge joining two nodes that are not adjacent in the cycle. An equivalent definition is that any chordless cycles have at most three nodes...

, an interval graph

Interval graph

In graph theory, an interval graph is the intersection graph of a multiset of intervals on the real line. It has one vertex for each interval in the set, and an edge between every pair of vertices corresponding to intervals that intersect.-Definition:...

, and a perfect graph

Perfect graph

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

.

The threshold graph

Threshold graph

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:#Addition of a single isolated vertex to the graph....

s are exactly the graphs that are both themselves trivially perfect and the complements of trivially perfect graphs.

Windmill graph

Windmill graph

In the mathematical field of graph theory, the windmill graph Wd is a simple undirected graph with n+1 vertices and nk/2 edges. It is defined for k ≥ 2 and n ≥ 2....

s are trivially perfect.

Recognition

describes a simple linear time algorithm for recognizing trivially perfect graphs, based on lexicographic breadth-first search

Lexicographic breadth-first search

In computer science, lexicographic breadth-first search or Lex-BFS is a linear time algorithm for ordering the vertices of a graph, that is used as part of other graph algorithms such as the recognition of chordal graphs and optimal coloring of distance-hereditary graphs...

. 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

Complement graph

In graph theory, the complement or inverse of a graph G is a graph H on the same vertices such that two 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...

of a trivially perfect graph, in linear time.