Lecture
In graph theory a perfect graph is a graph in which the chromatic number of every induced subgraph equals the size of the maximum clique of that subgraph. Thanks to the strong perfect graph theorem, it has been known since 2002 that perfect graphs — are the same thing as Berge graphs. A graph G is a Berge graph if neither G nor its complement has an induced cycle of odd length (5 or more edges).
Perfect graphs include many important families of graphs and provide a unification of results related to the coloring and cliques of these families. For example, in all perfect graphs the coloring problem, the maximum clique problem and the maximum independent set problem can be solved in polynomial time. In addition, some important minimax theorems of combinatorics, such as Dilworth's theorem, can be formulated in terms of perfect and some related graphs.
The theory of perfect graphs develops from the 1958 work of Tibor Gallai , which in modern language can be interpreted as the statement that the complement of a bipartite graph is a perfect graph. This result can be regarded as a simple equivalent of König's theorem, a considerably earlier result concerning matchings and vertex covers in bipartite graphs. The first use of the term «perfect graph» appeared in 1963 in an article by Claude Berge, from which the name «Berge graphs» arose. In that article he combined Gallai's result with some similar results by defining perfect graphs and conjectured the equivalence of perfect graphs and Berge graphs. The conjecture was proved in 2002 as the strong perfect graph theorem.
Some of the well-known perfect graphs:
In all graphs the clique number gives a lower bound on the chromatic number, since in a clique all vertices must be colored with different colors. Perfect graphs – are those for which the lower bound is tight not only for the whole graph, but also for all its induced subgraphs. For graphs that are not perfect, the chromatic number and the clique number may differ. So, for example, a cycle of length 5 requires 3 colors, while the maximum clique has size 2.
A proof that a graph is perfect can be regarded as a minimax theorem — the minimum number of colors required to color these graphs equals the size of the maximum clique. Many important minimax theorems of combinatorics can be expressed in these terms. For example, Dilworth's theorem states that the minimum number of chains when partitioning a partially ordered set into chains equals the maximum size of an antichain, and can be rephrased as the statement that the complements of comparability graphs are perfect. Mirsky's theorem states that the minimum number of antichains when partitioning 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 graphs is equivalent to the statement that in any sequence of ordered elements the length of the longest decreasing subsequence equals the minimum number of sequences when partitioning into increasing subsequences. The Erdős — Szekeres theorem is easily derived from this statement.
König's theorem in graph theory states that the minimum vertex cover of a bipartite graph corresponds to the maximum matching and vice versa. It can be interpreted as the perfection of complements of bipartite graphs. Another theorem on bipartite graphs, that the chromatic index equals the maximum degree of the graph, is equivalent to the perfection of the line graph of bipartite graphs.
In his first work on perfect graphs Berge made two important conjectures about their structure, and they were proved later.
The first of these theorems was the perfect graph theorem of László Lovász (1972), stating that a graph is perfect if and only if its complement is perfect. Thus, perfection (defined as the equality of the size of the maximum clique and the chromatic number in any induced subgraph) is equivalent to the equality of the size of the maximum independent set and the clique cover number.
The second theorem, stated by Berge as a conjecture, provided a forbidden-graph characterization of a perfect graph.
An induced cycle of odd length at least 5 is called an odd hole. An induced subgraph complementary to an odd hole is called an odd antihole. An odd cycle of length greater than 3 cannot be perfect, since its chromatic number equals three, while the clique number equals two. Similarly, the complement graph of an odd cycle of length 2k + 1 cannot be perfect, since its chromatic number equals k + 1, while its clique number equals k. (Or the imperfection of this graph follows from the perfect graph theorem and the imperfection of complements of odd cycles). Since these graphs are not perfect, every perfect graph must be a Berge graph, a graph without odd holes and without odd antiholes. Berge made the converse conjecture, that any Berge graph is perfect. This was finally proved by the strong perfect graph theorem of Chudnovsky , Robertson , Seymour, and Thomas (2006).
The perfect graph theorem has a short proof, but the proof of the strong perfect graph theorem is long and technically difficult. It is based on the structural decomposition of Berge graphs. Similar decomposition methods also arose as a result of studying other classes of graphs, in particular, claw-free graphs.
For all perfect graphs the graph coloring problem, the maximum clique problem and the maximum independent set problem can be solved in polynomial time (Grötschel, Lovász, Schrijver, 1988) . The algorithm for the general case uses the ellipsoid method for linear programming, but combinatorial algorithms known for many special cases are more efficient.
For many years the question of the computational complexity of recognizing Berge graphs and perfect graphs remained open. From the definition of Berge graphs it immediately follows that their recognition is a problem of the class co-NP . Finally, after the proof of the strong perfect graph theorem, a polynomial algorithm was found.
Perfect graphs are closely related to the theory of linear and integer programming . Both linear programs and integer programs are expressed in canonical form as the search for a vector 
which maximizes a linear objective function 
, subject to the linear constraints 
and 
. Here, A is given in the form of a matrix , and 
and 
are represented by two vectors. Although linear programs and integer programs are given in the same way, they differ in that in a linear program the solution vector may have arbitrary real numbers as coefficients, whereas in an integer program these unknown coefficients must be integers. This has a very strong effect on the computational complexity of these problems: linear programming can be solved in polynomial time , while integer programming — is NP-hard .
When the same given values A ,b , and care used to define both a linear program and an integer program, they usually have different optimal solutions. A linear program is called an integral linear program if the optimal solution of the integer program is also optimal for the linear program. (Otherwise the ratio between the two solution values is called the integrality gap and is important in the analysis of approximation algorithms for the integer program.) Perfect graphs can be used to characterize (0, 1) matrices. A (that is, matrices where all coefficients are 0 or 1) with the following property: if is a vector of all ones , then for all choices ofcthe resulting linear program is integral.
As Václav Chvátal proved , every matrix A with this property is (up to the removal of irrelevant «dominating» rows) the maximal-clique versus vertex incidence matrix of a perfect graph. This matrix has a column for each vertex of the graph and a row for each maximal clique, with a coefficient equal to one in the columns of the vertices belonging to the clique, and zero in the remaining columns. The integral linear programs encoded by this matrix search for the maximum-weight independent set of the given graph with weights given by the vector c .
For a matrix A defined in this way from a perfect graph, the set of vectors satisfying the system of inequalities , 
form an integral polytope . This is the convex hull of the indicator vectors of the independent sets in the graph, with facets corresponding to the maximal cliques in the graph. Perfect graphs — are the only graphs for which the two polytopes defined in this way, from independent sets and from maximal cliques, coincide.
Generalizing perfect graphs, a class of graphs is called χ-bounded if the chromatic number of the graphs in the class can be bounded by a function of their clique number. Perfect graphs are exactly those graphs for which this function is the identity .
The equality of the clique number and the chromatic number in perfect graphs motivated the definition of other classes of graphs in which other graph invariants are set equal to one another. For example, dominant perfect graphs are defined as graphs in which, in every induced subgraph, the smallest dominating set (a set of vertices adjacent to all the other vertices) equals the size of the smallest independent set that is a dominating set. These include, for example, claw-free graphs.
A trivially perfect graph — is a graph with the property that in every induced subgraph the size of the largest independent set equals the number of maximal cliques . Trivially perfect graphs were first studied by Wolk, but the name was given by Golumbic . Golumbic wrote that «this name is chosen in view of the triviality of the proof that such graphs are perfect » . Trivially perfect graphs are also known as comparability graphs of trees , arborescent comparability graphs and quasi-threshold graphs .
An edge-perfect graph — is a graph whose line graph is perfect . Equivalently, these are graphs in which every simple cycle of odd length is a triangle .
A graph is edge-perfect if and only if , any of its biconnected components is a bipartite graph , a complete graph. 
or a book of triangles 
. Since these three types of biconnected components are themselves perfect graphs, any edge-perfect graph is itself perfect . For the same reason any edge-perfect graph is a parity graph , a Meyniel graph and a perfectly orderable graph .
Edge-perfect graphs generalize bipartite graphs and share with them the properties that the maximum matching and the minimum vertex cover have the same size, and the chromatic index equals the maximum degree
Comments