Perfect graph Guide, Meaning , Facts, Information and Description
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.
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 length at least 4 has a chord, which is an edge not on the cycle but its endvertices are)
- Meyniel graphs (every cycle of odd length at least 5 has at least 2 chords)
- strongly perfect graphs (every induced subgraph has an independent set intersecting all its maximal cliquess)
Characterization of perfect graphs has 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 antihole 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.
Even though the conjecture has been settled, a lot of subtle structures and deep insights have emerged, and many problems remain open. For example, perfect graph recognition is known to be in
co-NP (Lovász 1983). But it is not known whether it is in
NP or
P.
See also
[1] The Strong Perfect Graph Theorem by Vašek Chvàtal, a major contributor to the subject
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; 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.
This is an Article on Perfect graph. Page Contains Information, Facts Details or Explanation Guide About Perfect graph
