Perfect graph
From Wikipedia, the free encyclopedia
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. That is, if every complete subgraph has at most k vertices, the graph can be colored with k colors, and this same relation between complete subgraphs and coloring holds in every induced subgraph of the graph.
In any graph, the clique number provides a lower bound for the chromatic number, as all vertices in a clique must be assigned distinct colors in any proper coloring. The perfect graphs are those for which this lower bound is tight, not just in the graph itself but in all of its induced subgraphs. For more general graphs, the chromatic number and clique number can differ; e.g., a cycle of length 5 requires three colors in any proper coloring but its largest clique has size 2.
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 (Grötschel, Lovász & Schrijver 1988). In addition, several important min-max theorems in combinatorics, such as Dilworth's theorem, can be expressed in terms of the perfection of certain associated graphs.
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 use of the phrase "perfect graph" appears to be in a 1963 paper of Claude Berge. In this paper he unified Gallai's result with several similar results by defining perfect graphs and conjecturing a characterization of these graphs that was later proven as the Strong Perfect Graph Theorem.
Contents |
[edit] Families of graphs that are perfect
Some of the more well-known perfect graphs are
- bipartite graphs
- The line graphs of bipartite graphs (see König's theorem)
- 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)
- distance-hereditary graphs
- permutation graphs
- comparability graphs (a vertex per element in a partial order, and an edge between any two comparable elements)
- wheel graphs with an odd number of vertices
- split graphs (graphs which can be partitioned into a clique and an independent set)
- Meyniel graphs (every cycle of odd length at least 5 has at least 2 chords)
- trivially perfect graphs (in every induced subgraph the size of the largest independent set equals the number of maximal cliques)
- strongly perfect graphs (every induced subgraph has an independent set intersecting all its maximal cliques)
- very strongly perfect graphs (in every induced subgraph, every vertex belongs to an independent set meeting all maximal cliques)
[edit] 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 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 as 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.)
[edit] External links
- The Strong Perfect Graph Theorem by Václav Chvátal.
- Open problems on perfect graphs, maintained by the American Institute of Mathematics.
- Perfect Problems, maintained by Václav Chvátal.
- Information System on Graph Class Inclusions: perfect graph
[edit] 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.
- Berge, Claude (1963). "Perfect graphs". Six Papers on Graph Theory: 1–21, Calcutta: Indian Statistical Institute.
- Chudnovsky, Maria; Cornuéjols, Gérard; Liu, Xinming; Seymour, Paul; Vušković, Kristina (2005). "Recognizing Berge graphs". Combinatorica 25: 143–186. doi:.
- Chudnovsky, Maria; Robertson, Neil; Seymour, Paul; Thomas, Robin (2006). "The strong perfect graph theorem". Annals of Mathematics 164: 51–229.
- Gallai, Tibor (1958). "Maximum-minimum Sätze über Graphen". Acta Math. Acad. Sci. Hungar. 9: 395–434. doi:.
- Golumbic, Martin Charles (1980), Algorithmic Graph Theory and Perfect Graphs, Academic Press, ISBN 0-444-51530-5, <http://www.elsevier.com/wps/find/bookdescription.cws_home/699916/description#description> Second edition, Annals of Discrete Mathematics 57, Elsevier, 2004.
- Grötschel, Martin; Lovász, László & Schrijver, Alexander (1988), Geometric Algorithms and Combinatorial Optimization, Springer-Verlag. See especially chapter 9, "Stable Sets in Graphs", pp. 273–303.
- Lovász, László (1972). "Normal hypergraphs and the perfect graph conjecture". Discrete Mathematics 2: 253–267. doi:.
- Lovász, László (1972). "A characterization of perfect graphs". Journal of Combinatorial Theory, Series B 13: 95–98. doi:.
- Lovász, László (1983). "Perfect graphs". Beineke, Lowell W.; Wilson, Robin J. (Eds.) Selected Topics in Graph Theory, Vol. 2: 55–87, Academic Press. ISBN 0-12-086202-6.
