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 subgraph In the mathematical field of graph theory, an induced subgraph of a graph is another graph, formed from a subset of the vertices of the graph and ''all'' of the edges (from the original graph) connecting pairs of vertices in that subset. Defini ...

s the size of the

maximum independent set In graph theory, an independent set, stable set, coclique or anticlique is a set of vertices in a graph, no two of which are adjacent. That is, it is a set S of vertices such that for every two vertices in S, there is no edge connecting the two ...

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 In mathematics, a well-order (or well-ordering or well-order relation) on a set ''S'' is a total order on ''S'' with the property that every non-empty subset of ''S'' has a least element in this ordering. The set ''S'' together with the well-orde ...

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 In the mathematical field of graph theory, a path graph or linear graph is a graph whose vertices can be listed in the order such that the edges are where . Equivalently, a path with at least two vertices is connected and has two terminal ...

or a

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 (at least 3, if the graph is simple) connected in a closed chain. The cycle graph with vertices is called ...

s. *They are the graphs in which every connected

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

. 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 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 In graph theory, graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called "colors" to elements of a graph subject to certain constraints. In its simplest form, it is a way of coloring the vertices o ...

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 In graph theory, a perfect graph is a graph in which the chromatic number of every induced subgraph equals the order of the largest clique of that subgraph (clique number). Equivalently stated in symbolic terms an arbitrary graph G=(V,E) is perfec ...

. 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 In computational complexity theory, a problem is NP-complete when: # it is a problem for which the correctness of each solution can be verified quickly (namely, in polynomial time) and a brute-force search algorithm can find a solution by tryi ...

, 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