HOME

TheInfoList



OR:

In
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 conn ...
, a perfect graph is a
graph Graph may refer to: Mathematics *Graph (discrete mathematics), a structure made of vertices and edges **Graph theory, the study of such graphs and their properties * Graph (topology), a topological space resembling a graph in the sense of discr ...
in which the chromatic number of every
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. Definit ...
equals the order of the largest
clique A clique ( AusE, CanE, or ), in the social sciences, is a group of individuals who interact with one another and share similar interests. Interacting with cliques is part of normative social development regardless of gender, ethnicity, or popula ...
of that subgraph (
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 compl ...
). Equivalently stated in symbolic terms an arbitrary graph G=(V,E) is perfect if and only if for all S\subseteq V we have \chi(G =\omega(G . The perfect graphs include many important families of graphs and serve to unify results relating
colorings Food coloring, or color additive, is any dye, pigment, or substance that imparts color when it is added to food or drink. They come in many forms consisting of liquids, powders, gels, and pastes. Food coloring is used in both commercial food ...
and cliques in those families. For instance, in all perfect graphs, the
graph coloring problem 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 ...
,
maximum clique problem In computer science, the clique problem is the computational problem of finding cliques (subsets of vertices, all adjacent to each other, also called complete subgraphs) in a graph. It has several different formulations depending on which cli ...
, and maximum independent set problem can all be solved in
polynomial 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 ...
. In addition, several important min-max theorems in combinatorics, such as
Dilworth's theorem In mathematics, in the areas of order theory and combinatorics, Dilworth's theorem characterizes the width of any finite partially ordered set in terms of a partition of the order into a minimum number of chains. It is named for the mathematicia ...
, can be expressed in terms of the perfection of certain associated graphs. A graph G is 1-perfect if and only if \chi(G)=\omega(G). Then, G is perfect if and only if every induced subgraph of G is 1-perfect.


Properties

* By the
perfect graph theorem In graph theory, the perfect graph theorem of states that an undirected graph is perfect if and only if its complement graph is also perfect. This result had been conjectured by , and it is sometimes called the weak perfect graph theorem to disti ...
, a graph G is perfect if and only if its
complement A complement is something that completes something else. Complement may refer specifically to: The arts * Complement (music), an interval that, when added to another, spans an octave ** Aggregate complementation, the separation of pitch-class ...
\bar is perfect. * By the strong perfect graph theorem, perfect graphs are the same as Berge graphs, which are graphs G where neither G nor \bar contains an induced cycle of odd length 5 or more. See below section for more details.


History

The theory of perfect graphs developed from a 1958 result of Tibor Gallai that in modern language can be interpreted as stating that the
complement A complement is something that completes something else. Complement may refer specifically to: The arts * Complement (music), an interval that, when added to another, spans an octave ** Aggregate complementation, the separation of pitch-class ...
of a
bipartite graph In the mathematical field of graph theory, a bipartite graph (or bigraph) is a graph whose vertices can be divided into two disjoint and independent sets U and V, that is every edge connects a vertex in U to one in V. Vertex sets U and V are ...
is perfect; this result can also be viewed as a simple equivalent of Kőnig's theorem, a much earlier result relating matchings and vertex covers in bipartite graphs. The first use of the phrase "perfect graph" appears to be in a 1963 paper of
Claude Berge Claude Jacques Berge (5 June 1926 – 30 June 2002) was a French mathematician, recognized as one of the modern founders of combinatorics and graph theory. Biography and professional history Claude Berge's parents were André Berge and Geneviè ...
, after whom Berge graphs are named. In this paper he unified Gallai's result with several similar results by defining perfect graphs, and he conjectured the equivalence of the perfect graph and Berge graph definitions; his conjecture was proved in 2002 as the strong perfect graph theorem.


Families of graphs that are perfect

Some of the more well-known perfect graphs are: *
Bipartite graph In the mathematical field of graph theory, a bipartite graph (or bigraph) is a graph whose vertices can be divided into two disjoint and independent sets U and V, that is every edge connects a vertex in U to one in V. Vertex sets U and V are ...
s, which are graphs that can be
colored ''Colored'' (or ''coloured'') is a racial descriptor historically used in the United States during the Jim Crow Era to refer to an African American. In many places, it may be considered a slur, though it has taken on a special meaning in South ...
with two colors, including
forests A forest is an area of land dominated by trees. Hundreds of definitions of forest are used throughout the world, incorporating factors such as tree density, tree height, land use, legal standing, and ecological function. The United Nations' ...
(graphs without cycles). *
Line graph In the mathematical discipline of graph theory, the line graph of an undirected graph is another graph that represents the adjacencies between edges of . is constructed in the following way: for each edge in , make a vertex in ; for ever ...
s of bipartite graphs (see Kőnig's theorem). Rook's graphs (line graphs of
complete bipartite graph In the mathematical field of graph theory, a complete bipartite graph or biclique is a special kind of bipartite graph where every vertex of the first set is connected to every vertex of the second set..Electronic edition page 17. Graph theory i ...
s) are a special case. * Chordal graphs, the graphs in which every cycle of four or more vertices has a ''chord'', an edge between two vertices that are not consecutive in the cycle. These include **forests, ''k''-trees (maximal graphs with a given
treewidth In graph theory, the treewidth of an undirected graph is an integer number which specifies, informally, how far the graph is from being a tree. The smallest treewidth is 1; the graphs with treewidth 1 are exactly the trees and the forests. The g ...
), **
split graph 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 , and independently introduced by . A split graph may have m ...
s (graphs that can be partitioned into a clique and an independent set), **
block graph In graph theory, a branch of combinatorial mathematics, a block graph or clique tree. is a type of undirected graph in which every biconnected component (block) is a clique. Block graphs are sometimes erroneously called Husimi trees (after ...
s (graphs in which every biconnected component is a clique), **
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 ...
s (graphs whose distances obey
Ptolemy's inequality In Euclidean geometry, Ptolemy's inequality relates the six distances determined by four points in the plane or in a higher-dimensional space. It states that, for any four points , , , and , the following inequality holds: :\overline\cdot \overli ...
), **
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 (graphs in which each vertex represents an interval of a line and each edge represents a nonempty intersection between two intervals), **
trivially perfect graph 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. Trivially perfect graphs were first studied by but were na ...
s (interval graphs for nested intervals), threshold graphs (graphs in which two vertices are adjacent when their total weight exceeds a numerical threshold), ** windmill graphs (formed by joining equal cliques at a common vertex), **and
strongly chordal graph In the mathematical area of graph theory, an undirected graph is strongly chordal if it is a chordal graph and every cycle of even length (≥ 6) in has an ''odd chord'', i.e., an edge that connects two vertices that are an odd distance (>1) a ...
s (chordal graphs in which every even cycle of length six or more has an odd chord). * Comparability graphs formed from
partially ordered set 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 ...
s by connecting pairs of elements by an edge whenever they are related in the partial order. These include: **bipartite graphs, complements of interval graphs, trivially perfect graphs, threshold graphs, windmill graphs, **
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 (graphs in which the edges represent pairs of elements that are reversed by a permutation), **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 (graphs formed by recursive operations of disjoint union and complementation). *
Perfectly orderable graph 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 sp ...
s, which are graphs that can be ordered in such a way that a
greedy coloring In the study of graph coloring problems in mathematics and computer science, a greedy coloring or sequential coloring is a coloring of the vertices of a graph formed by a greedy algorithm that considers the vertices of the graph in sequence and ...
algorithm is optimal on every induced subgraph. These include the bipartite graphs, the chordal graphs, the comparability graphs, **
distance-hereditary graph In graph theory, a branch of discrete mathematics, a distance-hereditary graph (also called a completely separable 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 ...
s (in which shortest path distances in connected induced subgraphs equal those in the whole graph), **and
wheel graph A wheel is a circular component that is intended to rotate on an axle bearing. The wheel is one of the key components of the wheel and axle which is one of the six simple machines. Wheels, in conjunction with axles, allow heavy objects to be ...
s with an odd number of vertices. * Trapezoid graphs, which are intersection graphs of
trapezoid A quadrilateral with at least one pair of parallel sides is called a trapezoid () in American and Canadian English. In British and other forms of English, it is called a trapezium (). A trapezoid is necessarily a convex quadrilateral in Eucl ...
s whose parallel pairs of edges lie on two parallel lines. These include the interval graphs, trivially perfect graphs, threshold graphs, windmill graphs, and permutation graphs; their complements are a subset of the comparability graphs.


Relation to min-max theorems

In all graphs, the clique number provides a lower bound for the chromatic number, as all vertices in a clique must be assigned distinct colors in any proper coloring. The perfect graphs are those for which this lower bound is tight, not just in the graph itself but in all of its induced subgraphs. For graphs that are not perfect, the chromatic number and clique number can differ; for instance, a cycle of length five requires three colors in any proper coloring but its largest clique has size two. A proof that a class of graphs is perfect can be seen as a min-max theorem: the minimum number of colors needed for these graphs equals the maximum size of a clique. Many important min-max theorems in combinatorics can be expressed in these terms. For instance,
Dilworth's theorem In mathematics, in the areas of order theory and combinatorics, Dilworth's theorem characterizes the width of any finite partially ordered set in terms of a partition of the order into a minimum number of chains. It is named for the mathematicia ...
states that the minimum number of chains in a partition of a
partially ordered set 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 ...
into chains equals the maximum size of an
antichain In mathematics, in the area of order theory, an antichain is a subset of a partially ordered set such that any two distinct elements in the subset are incomparable. The size of the largest antichain in a partially ordered set is known as its wid ...
, and can be rephrased as stating that the complements of comparability graphs are perfect. Mirsky's theorem states that the minimum number of antichains into a partition into antichains equals the maximum size of a chain, and corresponds in the same way to the perfection of comparability graphs. The perfection of
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 is equivalent to the statement that, in every sequence of ordered elements, the length of the longest decreasing subsequence equals the minimum number of sequences in a partition into increasing subsequences. The
Erdős–Szekeres theorem In mathematics, the Erdős–Szekeres theorem asserts that, given ''r'', ''s,'' any sequence of distinct real numbers with length at least (''r'' − 1)(''s'' − 1) + 1 contains a monotonically increasing sub ...
is an easy consequence of this statement. Kőnig's theorem in graph theory states that a minimum vertex cover in a bipartite graph corresponds to a
maximum matching Maximum cardinality matching is a fundamental problem in graph theory. We are given a graph , and the goal is to find a matching containing as many edges as possible; that is, a maximum cardinality subset of the edges such that each vertex is a ...
, and vice versa; it can be interpreted as the perfection of the complements of bipartite graphs. Another theorem about bipartite graphs, that their chromatic index equals their maximum degree, is equivalent to the perfection of the line graphs of bipartite graphs.


Characterizations and the perfect graph theorems

In his initial work on perfect graphs, Berge made two important conjectures on their structure that were only proved later. The first of these two theorems was the
perfect graph theorem In graph theory, the perfect graph theorem of states that an undirected graph is perfect if and only if its complement graph is also perfect. This result had been conjectured by , and it is sometimes called the weak perfect graph theorem to disti ...
of Lovász (1972), stating that a graph is perfect if and only if its
complement A complement is something that completes something else. Complement may refer specifically to: The arts * Complement (music), an interval that, when added to another, spans an octave ** Aggregate complementation, the separation of pitch-class ...
is perfect. Thus, perfection (defined as the equality of maximum clique size and chromatic number in every induced subgraph) is equivalent to the equality of maximum independent set size and clique cover number. The second theorem, conjectured by Berge, provided a
forbidden graph characterization In graph theory, a branch of mathematics, many important families of graphs can be described by a finite set of individual graphs that do not belong to the family and further exclude all graphs from the family which contain any of these forbidde ...
of perfect graphs. An induced cycle of odd length at least is called an odd hole. An induced subgraph that is the complement of an odd hole is called an odd antihole. An odd cycle of length greater than cannot be perfect, because its chromatic number is three and its clique number is two. Similarly, the complement of an odd cycle of length cannot be perfect, because its chromatic number is and its clique number is . (Alternatively, the imperfection of this graph follows from the perfect graph theorem and the imperfection of the complementary odd cycle). Because these graphs are not perfect, every perfect graph must be a Berge graph, a graph with no odd holes and no odd antiholes. Berge conjectured the converse, that every Berge graph is perfect. This was finally proven as the strong perfect graph theorem of Chudnovsky, Robertson, Seymour, and
Thomas Thomas may refer to: People * List of people with given name Thomas * Thomas (name) * Thomas (surname) * Saint Thomas (disambiguation) * Thomas Aquinas (1225–1274) Italian Dominican friar, philosopher, and Doctor of the Church * Thomas the A ...
(2006). It trivially implies the perfect graph theorem, hence the name. The perfect graph theorem has a short proof, but the proof of the strong perfect graph theorem is long and technical, based on a deep structural decomposition of Berge graphs. Related decomposition techniques have also borne fruit in the study of other graph classes, and in particular for the
claw-free graph In graph theory, an area of mathematics, a claw-free graph is a graph that does not have a claw as an induced subgraph. A claw is another name for the complete bipartite graph ''K''1,3 (that is, a star graph comprising three edges, three leaves, ...
s. There is a third theorem, again due to Lovász, which was originally suggested by Hajnal. It states that a graph is perfect if the sizes of the largest clique, and the largest independent set, when multiplied together, equal or exceed the number of vertices of the graph, and the same is true for any induced subgraph. It is an easy consequence of the strong perfect graph theorem, while the perfect graph theorem is an easy consequence of it. The Hajnal characterization is not met by odd -cycles or their complements for : the odd cycle on vertices has clique number and independence number . The reverse is true for the complement, so in both cases the product is .


Algorithms on perfect graphs

In all perfect graphs, the
graph coloring problem 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 ...
,
maximum clique problem In computer science, the clique problem is the computational problem of finding cliques (subsets of vertices, all adjacent to each other, also called complete subgraphs) in a graph. It has several different formulations depending on which cli ...
, and maximum independent set problem can all be solved in
polynomial 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 ...
. The algorithm for the general case involves the Lovász number of these graphs, which (for the complement of a given graph) is sandwiched between the chromatic number and clique number. Calculating the Lovász number can be formulated as a semidefinite program and approximated numerically in
polynomial 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 ...
using the
ellipsoid method In mathematical optimization, the ellipsoid method is an iterative method for convex optimization, minimizing convex functions. When specialized to solving feasible linear optimization problems with rational data, the ellipsoid method is an algor ...
for
linear programming Linear programming (LP), also called linear optimization, is a method to achieve the best outcome (such as maximum profit or lowest cost) in a mathematical model whose requirements are represented by linear relationships. Linear programming is ...
. For perfect graphs, rounding this approximation to an integer gives the chromatic number and clique number in polynomial time; the maximum independent set can be found by applying the same approach to the complement of the graph. However, this method is complicated and has a high polynomial exponent. More efficient combinatorial algorithms are known for many special cases. For many years the complexity of recognizing Berge graphs and perfect graphs remained open. From the definition of Berge graphs, it follows immediately that their recognition is in co-NP (Lovász 1983). Finally, subsequent to the proof of the strong perfect graph theorem, a polynomial time algorithm was discovered by Chudnovsky, Cornuéjols, Liu, Seymour, and Vušković.


References

* * * * * * Second edition, Annals of Discrete Mathematics 57, Elsevier, 2004. * See especially chapter 9, "Stable Sets in Graphs", pp. 273–303. * * * {{cite conference , author = Lovász, László , author-link = László Lovász , year = 1983 , title = Perfect graphs , editor1=Beineke, Lowell W. , editor2=Wilson, Robin J. , book-title = Selected Topics in Graph Theory, Vol. 2 , pages = 55–87 , publisher = Academic Press , isbn = 0-12-086202-6


External links


''The Strong Perfect Graph Theorem''
by Václav Chvátal.
Open problems on perfect graphs
maintained by the American Institute of Mathematics.
''Perfect Problems''
maintained by Václav Chvátal.