Perfect graph theorem

A perfect graph is an undirected graph in any generated subgraph of which the size of its largest click is equal to the minimum number of colors for coloring the subgraph. Perfect graphs include many important graph classes, which include bipartite graphs , chordal graphs, and comparability graphs .

The complement of a graph has an edge between two vertices if and only if the original graph does not have such an edge. Thus, a clique in the original graph becomes an independent set in the complement, and coloring of the original graph becomes the clique cover of the complement.

Perfect graph theorem states:

The complement of a perfect graph is perfect.

Equivalent wording: In a perfect graph, the size of the largest independent set is equal to the minimum number of clicks in the click coverage.

Let G be a graph-cycle of odd length greater than three (the so-called "odd hole"). Then, for any coloring G , at least three colors are required, but there is not a single triangle, so the graph is not perfect. By the perfect graph theorem, the complement of the graph G ("odd anti-hole") should therefore also be imperfect. If the graph G is a cycle of five vertices, it is isomorphic to its complement , but this is not true for longer cycles. A non-trivial task is to calculate the clique number and chromatic number in an odd anti-hole and an odd hole. According to the rigorous perfect graph theorem , odd holes and odd anti-holes turn out to be minimal forbidden generated subgraphs of perfect graphs.

In a nontrivial bipartite graph, the optimal number of colors (by definition) is two, and (since the bipartite graphs do not contain triangles ), the largest clique size is also two. Thus, any generated subgraph of a bipartite graph remains bipartite. Thus, bipartite graphs are perfect. In bipartite graphs with n vertices, the largest click coverage takes the form of the largest matching, along with an additional click for each uncovered vertex with size n - M , where M is the number of elements in the matching. In this case, the Koenig theorem follows from the perfect graph theorem that the size of a maximal independent set in a bipartite graph in a bipartite graph is also equal to n - M ^[6] , the result that was the main stimulus for Berge's formulation of the theory of perfect graphs.

describing the height of a partially ordered set in terms of partitioning into an can be formulated as the perfection of the comparability graph of a partially ordered set, and Dilworth’s theorems describing the width of a partially ordered set in terms of chaining can be formulated as the perfection of complements these graphs. Thus, the perfect graph theorem can be used to prove the Dilworth theorem, relying on the (simpler) proof of Mirsky’s theorem, or vice versa ^[7] .

To prove the perfect graph theorem, Lovash used the operation of replacing vertices in a graph with clicks. Berge already knew that if a graph is perfect, the graph obtained by such a replacement will also be perfect ^[8] . Any such replacement process can be broken down into repeated steps of duplicating vertices. If the duplicated vertex belongs to the largest clique of the graph, it increases the clique number and chromatic number by one. If, on the other hand, the duplicated vertex does not belong to the largest clique, we form a graph H by removing vertices of the same color as the duplicated (but not duplicated vertex itself) from the optimal coloring of the graph. The deleted vertices are included in all the largest cliques, so H has a number of clicks and the chromatic number is one less than in the original graph. Remote vertices and new copies of duplicated vertices can be added to a single color class, which indicates that the duplication step does not change the chromatic number. The same arguments show that doubling maintains equality of the number of clicks to the chromatic number in each generated subgraph of a given graph, so that each doubling step preserves the perfection of the graph ^[9] .

If a perfect graph G is given , Lovash forms a graph G * by replacing each vertex v with a clique with t _v vertices, where t _v is the number of different maximal different sets in G containing v . We can associate with each of the various maximal independent sets from G the maximum independent set in G * in such a way that the independent sets in G * will not all intersect and each vertex G * appears in a single selected set. That is, G * has a coloring in which each color class is a maximum independent set. Necessarily, this coloring will be the optimal coloring of G *. Since G is perfect, so is G *, and then it has a maximal clique K * whose size is equal to the number of colors in this coloring, which is equal to the number of different maximal independent sets in G. Necessarily, K * contains different representations for each of these maximal sets. The corresponding set of K vertices in G (vertices whose extended cliques in G * intersect K *) is a clique in G with the property that it intersects any maximal independent set in G. Thus, a graph formed from G by removing K has a clique coverage number not exceeding the clique number of G without a unit, and the independence number is at least one less than the independence number of G. The result follows from induction on this number ^[10]

The strong theorem on perfect graphs of Chudnovskaya, Robertson, Seymour and Thomas ^[11] states that a graph is perfect if and only if none of the generated subgraphs is a cycle of odd length greater than or equal to five, and also is not a complement to such a cycle . Since such a description is insensitive to the operation of complementing a graph, the weak theorem on perfect graphs immediately follows.

Cameron, Edmonds, and Lovash ^[12] proved that if the edges of a complete graph are divided into three subgraphs in such a way that any three vertices generate a connected graph in one of the three subgraphs, and if two of the subgraphs are perfect, then the third subgraph is also perfect. A perfect graph theorem is a special case of this result when one of the three graphs is .