Perfect graph

Encyclopedia : P : PE : PER : Perfect graph

In graph theory, a perfect graph is a graph in which the chromatic number of every induced subgraph equals the clique number of that subgraph.

These two numbers are obviously related since the chromatic number of a graph, i.e., the number of colors required so that adjacent vertices have different colors, is at least equal to the size of any clique in the graph, i.e., set of vertices that are all linked to each other. However, with general graphs, equality needs not hold as witnessed by a cyclic graph of length 5 with cliques of size 2 but where 3 colors are required.

Contents

1 Families of graphs that are perfect
2 Characterizations and the perfect graph theorems
3 Relevance
4 Related classes of graphs
5 External links
6 References

Families of graphs that are perfect

Some of the more well-known perfect graphs are

the line graph of a bipartite graph
interval graphs (vertices represent line intervals; and edges, their pairwise nonempty intersections)
chordal graphs (every cycle of four or more vertices has a chord, which is an edge between two nodes that are not adjacent in the cycle)
Meyniel graphs (every cycle of odd length at least 5 has at least 2 chords)
split graphs (graphs which can be partitioned into a clique and an independent set)
strongly perfect graphs (every induced subgraph has an independent set intersecting all its maximal cliques)

Characterizations and the perfect graph theorems

Characterization of perfect graphs has been known to be difficult. The first breakthrough was the affirmative answer to the then perfect graph conjecture.

Perfect Graph Theorem. (Lovász 1972)

A graph is perfect if and only if its complement is perfect.

An induced subgraph that is a cycle 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 to be the strong perfect graph conjecture and was finally answered in the affirmative in May, 2002.

Strong Perfect Graph Theorem. (Chudnovsky, Robertson, Seymour, Thomas 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 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.)

Relevance

Related classes of graphs

strongly perfect

:every induced subgraph H has an independent set meeting all maximal cliques of H.

trivially perfect

:for every induced subgraph H, the size of the largest independent set of H equals the number of maximal cliques of H

very strongly perfect

:for every induced subgraph H, every vertex of H belongs to an independent set of H meeting all maximal cliques of H.

External links

[The Strong Perfect Graph Theorem] by Vašek Chvátal.
[Open problems on perfect graphs], maintained by the American Institute of Mathematics.
[Perfect Problems], maintained by Vašek Chvátal.

References

Berge, Claude (1961). Färbung von Graphen, deren sämtliche bzw. deren ungerade Kreise starr sind. Wiss. Z. Martin-Luther-Univ. Halle-Wittenberg Math.-Natur. Reihe 10, 114.
Chudnovsky, Maria; Cornuéjols, Gérard; Liu, Xinming; Seymour, Paul; Vušković, Kristina (2005). Recognizing Berge graphs. Combinatorica 25, 143–186.
Chudnovsky, Maria; Robertson, Neil; Seymour, Paul; Thomas, Robin (announced May 2002, revised March 26, 2004). The strong perfect graph theorem.
Lovász, László (1972). Normal hypergraphs and the perfect graph conjecture. Discrete Math. 2, 253–267.
Lovász, László (1972). A characterization of perfect graphs. J. Combin. Theory (B) 13, 95–98.
Lovász, László (1983). Perfect graphs. In Beineke, Lowell W.; Wilson, Robin J. (Eds), Selected Topics in Graph Theory, Vol. 2, 55–87. Academic Press. ISBN 0-12-086202-6.

From Wikipedia, the Free Encyclopedia. Original article here. Support Wikipedia by contributing or donating.
All text is available under the terms of the GNU Free Documentation License See Wikipedia Copyrights for details.