graph theory In mathematics, graph theory is the study of ''graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conne ...

, 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 clique In the mathematical area of graph theory, a clique ( or ) is a subset of vertices of an undirected graph such that every two distinct vertices in the clique are adjacent. That is, a clique of a graph G is an induced subgraph of G that is comple ...

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

s of order-theoretic trees. That is, let be a

partial order In mathematics, especially order theory, a partially ordered set (also poset) formalizes and generalizes the intuitive concept of an ordering, sequencing, or arrangement of the elements of a set. A poset consists of a set together with a binary ...

such that for each , the set is well-ordered by the

relation Relation or relations may refer to: General uses *International relations, the study of interconnection of politics, economics, and law on a global level *Interpersonal relationship, association or acquaintance between two or more people *Public ...

, and also possesses a minimum element . Then the comparability graph of is trivially perfect, and every trivially perfect graph can be formed in this way. *They are the graphs that do not have a path graph or a cycle graph as induced subgraphs. *They are the graphs in which every connected induced subgraph contains a

universal vertex 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. (It is not to be confused ...

. *They are the graphs that can be represented as the

interval graph 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. Int ...

s for a set of nested

intervals Interval may refer to: Mathematics and physics * Interval (mathematics), a range of numbers ** Partially ordered set#Intervals, its generalization from numbers to arbitrary partially ordered sets * A statistical level of measurement * Interval est ...

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

and

cograph In graph theory, a cograph, or complement-reducible graph, or ''P''4-free graph, is a graph that can be generated from the single-vertex graph ''K''1 by complementation and disjoint union. That is, the family of cographs is the smallest class of ...

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 In the mathematical area of graph theory, an induced path in an undirected graph is a path that is an induced subgraph of . That is, it is a sequence of vertices in such that each two adjacent vertices in the sequence are connected by an edge ...

s on four vertices (). *They are the graphs that are both cographs and interval graphs., p. 248; , theorem 3. *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 , the

neighborhoods A neighbourhood (British English, Irish English, Australian English and Canadian English) or neighborhood (American English; American and British English spelling differences, see spelling differences) is a geographically localised community ...

of and (including and themselves) are nested: one neighborhood must be a subset of the other. *They are the

permutation graph In the mathematical field of graph theory, 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 d ...

s defined from

stack-sortable permutation In mathematics and computer science, a stack-sortable permutation (also called a tree permutation) is a permutation whose elements may be sorted by an algorithm whose internal storage is limited to a single stack data structure. The stack-sortab ...

s. *They are the graphs with the property that in each of its induced subgraphs the

clique cover number In graph theory, a clique cover or partition into cliques of a given undirected graph is a partition of the vertices into cliques, subsets of vertices within which every two vertices are adjacent. A minimum clique cover is a clique cover that use ...

equals the number of

s. *They are the graphs with the property that in each of its induced subgraphs the

clique number In the mathematical area of graph theory, a clique ( or ) is a subset of vertices of an undirected graph such that every two distinct vertices in the clique are adjacent. That is, a clique of a graph G is an induced subgraph of G that is comple ...

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

, a

chordal graph 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 cy ...

, a

Ptolemaic graph In graph theory, a Ptolemaic graph is an undirected graph whose shortest path distances obey Ptolemy's inequality, which in turn was named after the Greek astronomer and mathematician Ptolemy. The Ptolemaic graphs are exactly the graphs that ar ...

, an

, and a perfect graph. The

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. # Addition of a single dominating vertex t ...

s are exactly the graphs that are both themselves trivially perfect and the complements of trivially perfect graphs (co-trivially perfect graphs)., theorem 6.6.3, p. 100; , corollary 5.

Windmill graph In the mathematical field of graph theory, the windmill graph is an undirected graph constructed for and by joining copies of the complete graph at a shared universal vertex. That is, it is a 1-clique-sum of these complete graphs. Propert ...

s are trivially perfect.

Recognition

describes a simple

linear time In computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by ...

algorithm for recognizing trivially perfect graphs, based on

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. The algorithm is different from a breadth-first search, but it produces an ordering that is consistent with breadt ...

. 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 In the mathematical field of graph theory, the complement or inverse of a graph is a graph on the same vertices such that two distinct vertices of are adjacent if and only if they are not adjacent in . That is, to generate the complement of a ...

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

* {{citation , contribution-url = http://www.graphclasses.org/classes/gc_327.html , contribution = Trivially perfect graphs , url = http://www.graphclasses.org/classes/gc_327.html , title = Information System on Graph Classes and their Inclusions Graph families Perfect graphs