graph theory In mathematics and computer science, graph theory is the study of ''graph (discrete mathematics), graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of ''Vertex (graph ...

, a trivially perfect graph is a graph with the property that in each of its

induced subgraph In 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. Definition Formally, let G=(V,E) ...

s the size of the

maximum independent set In mathematical analysis, the maximum and minimum of a function are, respectively, the greatest and least value taken by the function. Known generically as extremum, they may be defined either within a given range (the ''local'' or ''relative ...

equals the number of

maximal clique In 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 complete. Cliques are one of t ...

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 Perfect commonly refers to: * Perfection; completeness, and excellence * Perfect (grammar), a grammatical category in some languages Perfect may also refer to: Film and television * ''Perfect'' (1985 film), a romantic drama * ''Perfect'' (20 ...

." 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 and order 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, partial ...

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

partial order In mathematics, especially order theory, a partial order on a set is an arrangement such that, for certain pairs of elements, one precedes the other. The word ''partial'' is used to indicate that not every pair of elements needs to be comparable ...

such that for each , the set is

well-ordered In mathematics, a well-order (or well-ordering or well-order relation) on a set is a total ordering on with the property that every non-empty subset of has a least element in this ordering. The set together with the ordering is then called a ...

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

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

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 (graph theory), 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. A ...

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

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

. 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 (Commonwealth English) or neighborhood (American English) is a geographically localized community within a larger town, city, suburb or rural area, sometimes consisting of a single street and the buildings lining it. Neighbourh ...

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

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 collection of cliques that cover the whole graph. A minimum clique cover is a clique cover that uses as few cliques as possible. The minimum for which a cl ...

equals the number of

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

clique number In 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 complete. Cliques are one of t ...

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 methodic assignment of labels traditionally called "colors" to elements of a graph. The assignment is subject to certain constraints, such as that no two adjacent elements have the same color. Graph coloring i ...

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

, an

, and a

perfect graph In graph theory, a perfect graph is a Graph (discrete mathematics), graph in which the Graph coloring, chromatic number equals the size of the maximum clique, both in the graph itself and in every induced subgraph. In all graphs, the chromatic nu ...

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

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

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

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

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, NP-complete problems are the hardest of the problems to which ''solutions'' can be verified ''quickly''. Somewhat more precisely, a problem is NP-complete when: # It is a decision problem, meaning that for any ...

, 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