Perfect graph

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 clique, in the complement graph, corresponds to an independent set in the given.

More strongly, the same thing is true in every induced subgraph of the complement graph.

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.

[7] 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;[8] 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,[9] and the first use of the phrase "perfect graph" appears to be in a 1963 paper of Berge.

[5] 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.

[13] The conjectured strong perfect graph theorem became the focus of research in the theory of perfect graphs for many years,[12] until its proof was announced in 2002 by Maria Chudnovsky, Neil Robertson, Paul Seymour, and Robin Thomas,[14] and published by them in 2006.

[16] 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.

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.

The equality of maximum degree and chromatic index, in bipartite graphs, is another theorem of Dénes Kőnig.

According to the structural decomposition of perfect graphs used as part of this proof, every perfect graph that is not already in one of these four classes can be decomposed by partitioning its vertices into subsets, in one of four ways, called a 2-join, the complement of a 2-join, a homogeneous pair, or a skew partition.

[23] A clique, in a comparability graph, comes from a subset of elements that are all pairwise comparable; such a subset is called a chain, and it is linearly ordered by the given partial order.

Dilworth's theorem, in the theory of partial orders, states that for every finite partial order, the size of the largest antichain equals the minimum number of chains into which the elements can be partitioned.

Similarly, Mirsky's theorem states that for every finite partial order, the size of the largest chain equals the minimum number of antichains into which the elements can be partitioned, or that every finite incomparability graph is perfect.

[26] A clique, in a permutation graph, is a subsequence of elements that appear in increasing order in the given permutation, and an independent set is a subsequence of elements that appear in decreasing order.

These have been used to model human preferences under the assumption that, when items have utilities that are very close to each other, they will be incomparable.

In this way, it has been shown that almost all perfect graphs contain a Hamiltonian cycle.

occurs as an induced subgraph of a large random perfect graph is 0, 1/2, or 1, respectively as

This property is generalized in the family of perfectly orderable graphs, the graphs for which there exists an ordering that, when restricted to any induced subgraph, causes greedy coloring to be optimal.

Parity graphs are Meyniel graphs, and therefore perfect: if a long odd cycle had only one chord, the two parts of the cycle between the endpoints of the chord would be induced paths of different parity.

(Otherwise, the ratio between the two solution values is called the integrality gap, and is important in analyzing approximation algorithms for the integer program.)

with this property is (up to removal of irrelevant "dominated" rows) the maximal clique versus vertex incidence matrix of a perfect graph.

The integral linear programs encoded by this matrix seek the maximum-weight independent set of the given graph, with weights given by the vector

The algorithm for the general case involves the Lovász number of these graphs.

The Lovász number of any graph can be determined by labeling its vertices by high dimensional unit vectors, so that each two non-adjacent vertices have perpendicular labels, and so that all of the vectors lie in a cone with as small an opening angle as possible.

Thus, they can be computed by approximating the Lovász number accurately enough and rounding the result to the nearest integer.

However, solving these problems using the Lovász number and the ellipsoid method is complicated and has a high polynomial exponent.

[6] After the strong perfect graph theorem was proved, Chudnovsky, Cornuéjols, Liu, Seymour, and Vušković discovered a polynomial time algorithm for testing the existence of odd holes or anti-holes.