|
|
|
|
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.
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.
Discussion
Ask a question about 'Perfect graph' Start a new discussion about 'Perfect graph' Answer questions from other users |
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.
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 . 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.
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 that can be partitioned into a clique and an independent set)
- perfectly orderable graphs (graphs that can be ordered in such a way that a greedy coloring algorithm is optimal on every induced subgraph)
- 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)
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 Vukovic shortly afterwards, independent of the Strong Perfect Graph Theorem.)
External links
|
| |
|
|
