Perfect graph
Encyclopedia
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 perfect graph is a graph
Graph (mathematics)
In mathematics, a graph is an abstract representation of a set of objects where some pairs of the objects are connected by links. The interconnected objects are represented by mathematical abstractions called vertices, and the links that connect some pairs of vertices are called edges...
in which the chromatic number
Graph coloring
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 of a graph such that no two adjacent vertices share the...
of every induced subgraph equals the size of the largest clique of that subgraph.
In any graph, 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 more general graphs, the chromatic number and clique number can differ; e.g., a cycle of length 5 requires three colors in any proper coloring but its largest clique has size 2.
Perfect graphs include many important families of graphs, and serve to unify results relating colorings and cliques in those families. For instance, in all perfect graphs, the graph coloring problem, maximum clique problem, and maximum independent set problem can all be solved in polynomial time . In addition, several important min-max theorems in combinatorics
Combinatorics
Combinatorics is a branch of mathematics concerning the study of finite or countable discrete structures. Aspects of combinatorics include counting the structures of a given kind and size , deciding when certain criteria can be met, and constructing and analyzing objects meeting the criteria ,...
, such as Dilworth's theorem
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...
, can be expressed in terms of the perfection of certain associated graphs.
The theory of perfect graphs developed from a 1958 result of Tibor Gallai
Tibor Gallai
Tibor Gallai was a Hungarian mathematician. He worked in combinatorics, especially in graph theory, and was a lifelong friend and collaborator of Paul Erdős. He was a student of Dénes König and an advisor of László Lovász...
that in modern language can be interpreted as stating that the complement
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 bipartite graph
Bipartite graph
In the mathematical field of graph theory, a bipartite graph is a graph whose vertices can be divided into two disjoint sets U and V such that every edge connects a vertex in U to one in V; that is, U and V are independent sets...
is perfect; this result can also be viewed as a simple equivalent of König's theorem
König's theorem (graph theory)
In the mathematical area of graph theory, König's theorem, proved by Dénes Kőnig in 1931, describes an equivalence between the maximum matching problem and the minimum vertex cover problem in bipartite graphs...
, 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 Berge
Claude Berge was a French mathematician, recognized as one of the modern founders of combinatorics and graph theory. He is particularly remembered for his famous conjectures on perfect graphs and for Berge's lemma, which states that a matching M in a graph G is maximum if and only if there is in...
. In this paper he unified Gallai's result with several similar results by defining perfect graphs and conjecturing a characterization of these graphs that was later proven as the Strong Perfect Graph Theorem.
Families of graphs that are perfect
Some of the more well-known perfect graphs are- bipartite graphBipartite graphIn the mathematical field of graph theory, a bipartite graph is a graph whose vertices can be divided into two disjoint sets U and V such that every edge connects a vertex in U to one in V; that is, U and V are independent sets...
s - The line graphLine graphIn graph theory, the line graph L of undirected graph G is another graph L that represents the adjacencies between edges of G...
s of bipartite graphs (see König's theoremKönig's theorem (graph theory)In the mathematical area of graph theory, König's theorem, proved by Dénes Kőnig in 1931, describes an equivalence between the maximum matching problem and the minimum vertex cover problem in bipartite graphs...
) - interval graphInterval graphIn 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 (vertices represent line intervals; and edges, their pairwise nonempty intersections) - chordal graphChordal graphIn 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...
s (every cycle of four or more vertices has a chord, which is an edge between two nodes that are not adjacent in the cycle) - distance-hereditary graphDistance-hereditary graphIn graph-theoretic mathematics, a distance-hereditary graph is a graph in which the distances in any connected induced subgraph are the same as they are in the original graph...
s - permutation graphPermutation graphIn areas of mathematics influenced by graph theory, a permutation graph is the intersection graph of a family of line segments that connect two parallel lines in the Euclidean plane...
s - trapezoid graphTrapezoid graphIn graph theory, trapezoid graphs are intersection graphs of trapezoids between two horizontal lines. They are a class of co-comparability graphs that contain interval graphs and permutation graphs as subclasses...
s - comparability graphComparability graphIn 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 (a vertex per element in a partial order, and an edge between any two comparable elements) - wheel graphWheel graphIn the mathematical discipline of graph theory, a wheel graph Wn is a graph with n vertices, formed by connecting a single vertex to all vertices of an -cycle. The numerical notation for wheels is used inconsistently in the literature: some authors instead use n to refer to the length of the cycle,...
s with an odd number of vertices - split graphSplit graphIn 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...
s (graphs that can be partitioned into a clique and an independent set) - perfectly orderable graphs (graphs that can be ordered in such a way that a greedy coloringGreedy coloringIn the study of graph coloring problems in mathematics and computer science, a greedy 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 assigns each vertex its first available color...
algorithm is optimal on every induced subgraph) - trivially perfect graphs (in every induced subgraph the size of the largest independent set equals the number of maximal cliques)
- Meyniel graphs (every cycle of odd length at least 5 has at least 2 chords)
- strongly perfect graphs (every induced subgraph has an independent set intersecting all its maximal cliques)
- very strongly perfect graphs (in every induced subgraph, every vertex belongs to an independent set meeting all maximal cliques).
Characterizations and the perfect graph theorems
Characterization of perfect graphs was a longstanding open problem. The first breakthrough was the affirmative answer to the then perfect graph conjecture.Perfect Graph Theorem. (Lovász
Lovász
Lovász :* Lázár Lovász , a Hungarian athlete who competed in hammer throw* László Lovász , a mathematician, best known for his work in combinatorics,** Lovász conjecture ** Erdős–Faber–Lovász conjecture...
1972)
- A graph is perfect if and only ifIf and only ifIn logic and related fields such as mathematics and philosophy, if and only if is a biconditional logical connective between statements....
its complementGlossary of graph theoryGraph theory is a growing area in mathematical research, and has a large specialized vocabulary. Some authors use the same word with different meanings. Some authors use different words to mean the same thing. This page attempts to keep up with current usage....
is perfect.
An induced cycle
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...
of odd length at least 5 is called an odd hole. An induced subgraph that is the complement of an odd hole is called an odd antihole. A graph that does not contain any odd holes or odd antiholes is called a Berge graph. By virtue of the perfect graph theorem, a perfect graph is necessarily a Berge graph. But it puzzled people for a long time whether the converse was true. This was known as the strong perfect graph conjecture and was finally answered in the affirmative in May, 2002.
Strong Perfect Graph Theorem. (Chudnovsky
Maria Chudnovsky
Maria Chudnovsky is an Israeli mathematician. She is professor in the departments of mathematics and of industrial engineering and operations research at Columbia University. She grew up in Russia and Israel, studying at the Technion, and received her Ph.D. in 2003 from Princeton University under...
, Robertson
Neil Robertson (mathematician)
G. Neil Robertson is a mathematician working mainly in topological graph theory, currently a distinguished professor at the Ohio State University. He earned his Ph.D. in 1969 at the University of Waterloo under his doctoral advisor William Tutte. According to the criteria of the Erdős Number...
, Seymour, Thomas
Robin Thomas (mathematician)
Robin Thomas is a mathematician working in graph theory at the Georgia Institute of Technology.Thomas received his doctorate in 1985 from Charles University in Prague, Czechoslovakia , under the supervision of Jaroslav Nešetřil...
2002)
- A graph is perfect if and only if it is a Berge graph.
As with many results discovered through structural methods, the theorem's proof is long and technical. Efforts towards solving the problem have led to deep insights in the field of structural graph theory, where many related problems remain open. For example, it was proved some time ago that the problem of recognizing Berge graphs is in co-NP (Lovász 1983), but it was not known whether or not it is in P
P (complexity)
In computational complexity theory, P, also known as PTIME or DTIME, is one of the most fundamental complexity classes. It contains all decision problems which can be solved by a deterministic Turing machine using a polynomial amount of computation time, or polynomial time.Cobham's thesis holds...
until after the proof of the Strong Perfect Graph Theorem appeared. (A polynomial time algorithm was discovered by Chudnovsky, Cornuéjols, Liu, Seymour, and Vušković shortly afterwards, independent of the Strong Perfect Graph Theorem.)
External links
- The Strong Perfect Graph Theorem by Václav ChvátalVáclav ChvátalVáclav Chvátal is a professor in the Department of Computer Science and Software Engineering at Concordia University in Montreal, Canada, where he holds theCanada Research Chair in Combinatorial Optimization....
. - Open problems on perfect graphs, maintained by the American Institute of MathematicsAmerican Institute of MathematicsThe American Institute of Mathematics was founded in 1994 by John Fry and is located in Palo Alto, California. Privately funded by Fry at inception, in 2002, AIM became one of eight NSF-funded mathematical institutes....
. - Perfect Problems, maintained by Václav Chvátal.
- Information System on Graph Class Inclusions: perfect graph