In graph theory, a perfect graph is a graph in which the chromatic number equals the size of the maximum clique, both in the graph itself and in every induced subgraph. In all graphs, the chromatic number is greater than or equal to the size of the maximum clique, but they can be far apart. A graph is perfect when these numbers are equal, and remain equal after the deletion of arbitrary subsets of vertices.
The 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, despite their greater complexity for non-perfect graphs. In addition, several important minimax theorems in combinatorics, including Dilworth's theorem and Mirsky's theorem on partially ordered sets, Kőnig's theorem on matchings, and the Erdős–Szekeres theorem on monotonic sequences, can be expressed in terms of the perfection of certain associated graphs.
The perfect graph theorem states that the complement graph of a perfect graph is also perfect. The strong perfect graph theorem characterizes the perfect graphs in terms of certain forbidden induced subgraphs, leading to a polynomial time algorithm for testing whether a graph is perfect.
Definitions and characterizations
A clique in an undirected graph is a subset of its vertices that are all adjacent to each other, such as the subsets of vertices connected by heavy edges in the illustration. The clique number is the number of vertices in the largest clique: two in the illustrated seven-vertex cycle, and three in the other graph shown. A graph coloring assigns a color to each vertex so that each two adjacent vertices have different colors, also shown in the illustration. The chromatic number of a graph is the minimum number of colors in any coloring. The colorings shown are optimal, so the chromatic number is three for the 7-cycle and four for the other graph shown. The vertices of any clique must have different colors, so the chromatic number is always greater than or equal to the clique number. For some graphs, they are equal; for others, such as the ones shown, they are unequal. The perfect graphs are defined as the graphs for which these two numbers are equal, not just in the graph itself, but in every induced subgraph obtained by deleting some of its vertices.
The perfect graph theorem asserts that the complement graph of a perfect graph is itself perfect. The complement graph has an edge between two vertices if and only if the given graph does not. A clique, in the complement graph, corresponds to an independent set in the given. A coloring of the complement graph corresponds to a clique cover, a partition of the vertices of the given graph into cliques. The fact that the complement of a perfect graph is also perfect implies that, in itself, the independence number (the size of its maximum independent set), equals its clique cover number (the fewest number of cliques needed in a clique cover). More strongly, the same thing is true in every induced subgraph of the complement graph. This provides an alternative and equivalent definition of the perfect graphs: they are the graphs for which, in each induced subgraph, the independence number equals the clique cover number.
The strong perfect graph theorem gives a different way of defining perfect graphs, by their structure instead of by their properties. It is based on the existence of cycle graphs and their complements within a given graph. A cycle of odd length, greater than three, is not perfect: its clique number is two, but its chromatic number is three. By the perfect graph theorem, the complement of an odd cycle of length greater than three is also not perfect. The complement of a length-5 cycle is another length-5 cycle, but for larger odd lengths the complement is not a cycle; it is called an anticycle. The strong perfect graph theorem asserts that these are the only forbidden induced subgraphs for the perfect graphs: a graph is perfect if and only if its induced subgraphs include neither an odd cycle nor an odd anticycle of five or more vertices. In this context, induced cycles that are not triangles are called "holes", and their complements are called "antiholes", so the strong perfect graph theorem can be stated more succinctly: a graph is perfect if and only if it has neither an odd hole nor an odd antihole.
These results can be combined in another characterization of perfect graphs: they are the graphs for which the product of the clique number and independence number is greater than or equal to the number of vertices, and for which the same is true for all induced subgraphs. Because the statement of this characterization remains invariant under complementation of graphs, it implies the perfect graph theorem. One direction of this characterization follows easily from the original definition of perfect: the number of vertices in any graph equals the sum of the sizes of the color classes in an optimal coloring, and is less than or equal to the number of colors multiplied by the independence number. In a perfect graph, the number of colors equals the clique number, and can be replaced by the clique number in this inequality. The other direction can be proved directly, but it also follows from the strong perfect graph theorem: if a graph is not perfect, it contains an odd cycle or its complement, and in these subgraphs the product of the clique number and independence number is one less than the number of vertices.
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 of a bipartite graph 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 formulation of the concept of perfect graphs more generally was in a 1961 paper by Claude Berge, in German, and the first use of the phrase "perfect graph" appears to be in a 1963 paper of Berge. In these works he unified Gallai's result with several similar results by defining perfect graphs, and he conjectured both the perfect graph theorem and the strong perfect graph theorem. In formulating these concepts, Berge was motivated by the concept of the Shannon capacity of a graph, by the fact that for (co-)perfect graphs it equals the independence number, and by the search for minimal examples of graphs for which this is not the case.; note that Chudnovsky et al define capacity using the complement of the graphs used for the definition in Shannon capacity of a graph, and include a logarithm that the linked article does not include. Until the strong perfect graph theorem was proven, the graphs described by it (that is, the graphs with no odd hole and no odd antihole) were called Berge graphs.
The perfect graph theorem was proven by László Lovász in 1972, who in the same year proved the stronger inequality between the number of vertices and the product of the clique number and independence number, without benefit of the strong perfect graph theorem. In 1991, Alfred Lehman won the Fulkerson Prize, sponsored jointly by the Mathematical Optimization Society and American Mathematical Society, for his work on generalizations of the theory of perfect graphs to logical matrices. The conjectured strong perfect graph theorem became the focus of research in the theory of perfect graphs for many years, until its proof was announced in 2002 by Maria Chudnovsky, Neil Robertson, Paul Seymour, and Robin Thomas, and published by them in 2006. This work won its authors the 2009 Fulkerson Prize. 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 graphs. The symmetric characterization of perfect graphs in terms of the product of clique number and independence number was originally suggested by Hajnal and proven by Lovász.
Families of graphs Many well-studied families of graphs are perfect, and in many cases the fact that these graphs are perfect corresponds to a minimax theorem for some kinds of combinatorial structure defined by these graphs. Examples of this phenomenon include the perfection of bipartite graphs and their line graphs, associated with Kőnig's theorem relating maximum matchings and vertex covers in bipartite graphs, and the perfection of comparability graphs, associated with Dilworth's theorem and Mirsky's theorem on chains and antichains in partially ordered sets. Other important classes of graphs, defined by having a structure related to the holes and antiholes of the strong perfect graph theorem, include the chordal graphs, Meyniel graphs, and their subclasses.
Bipartite graphs and line graphs
In bipartite graphs (with at least one edge) the chromatic number and clique number both equal two. Their induced subgraphs remain bipartite, so bipartite graphs are perfect. Other important families of graphs are bipartite, and therefore also perfect, including for instance the trees and median graphs. By the perfect graph theorem, maximum independent sets in bipartite graphs have the same size as their minimum clique covers. The maximum independent set is complementary to a minimum vertex cover, a set of vertices that touches all edges. A minimum clique cover consists of a maximum matching (as many disjoint edges as possible) together with one-vertex cliques for all remaining vertices, and its size is the number of vertices minus the number of matching edges. Therefore, this equality can be expressed equivalently as an equality between the size of the maximum matching and the minimum vertex cover in bipartite graphs, the usual formulation of Kőnig's theorem.
A matching, in any graph , is the same thing as an independent set in the line graph , a graph that has a vertex for each edge in and an edge between two vertices in for each pair of edges in that share an endpoint. Line graphs have two kinds of cliques: sets of edges in with a common endpoint, and triangles in . In bipartite graphs, there are no triangles, so a clique cover in corresponds to a vertex cover in . Therefore, in line graphs of bipartite graphs, the independence number and clique cover number are equal. Induced subgraphs of line graphs of bipartite graphs are line graphs of subgraphs, so the line graphs of bipartite graphs are perfect. Examples include the rook's graphs, the line graphs of complete bipartite graphs. Every line graph of a bipartite graph is an induced subgraph of a rook's graph.
Because line graphs of bipartite graphs are perfect, their clique number equals their chromatic number. The clique number of the line graph of a bipartite graph is the maximum degree of any vertex of the underlying bipartite graph. The chromatic number of the line graph of a bipartite graph is the chromatic index of the underlying bipartite graph, the minimum number of colors needed to color the edges so that touching edges have different colors. Each color class forms a matching, and the chromatic index is the minimum number of matchings needed to cover all edges. The equality of maximum degree and chromatic index, in bipartite graphs, is another theorem of Dénes Kőnig. In arbitrary simple graphs, they can differ by one; this is Vizing's theorem.
The underlying graph of a perfect line graph is a line perfect graph. These are the graphs whose biconnected components are bipartite graphs, the complete graph , and triangular books, sets of triangles sharing an edge. These components are perfect, and their combination preserves perfection, so every line perfect graph is perfect.