FACTOID # 22: South Dakota has the highest employment ratio in America, but the lowest median earnings of full-time male employees.
 Home   Encyclopedia   Statistics   States A-Z   Flags   Maps   FAQ   About 


FACTS & STATISTICS    Advanced view

Search encyclopedia, statistics and forums:



(* = Graphable)



Encyclopedia > 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.

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 cliques)

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] (http://www.cs.rutgers.edu/~chvatal/perfect/spgt.html) The Strong Perfect Graph Theorem by Vašek Chvŕtal, a major contributor to the subject


  • 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.

  Results from FactBites:
Graph theory - Wikipedia, the free encyclopedia (1209 words)
Informally, a graph is a set of objects called vertices (or nodes) connected by links called edges (or arcs) which can be directed (assigned a direction).
Graphs are represented graphically by drawing a dot for every vertex, and drawing an arc between two vertices if they are connected by an edge.
A graph drawing should not be confused with the graph itself (the abstract, non-graphical structure) as there are several ways to structure the graph drawing.
  More results at FactBites »



Share your thoughts, questions and commentary here
Your name
Your comments

Want to know more?
Search encyclopedia, statistics and forums:


Press Releases |  Feeds | Contact
The Wikipedia article included on this page is licensed under the GFDL.
Images may be subject to relevant owners' copyright.
All other elements are (c) copyright NationMaster.com 2003-5. All Rights Reserved.
Usage implies agreement with terms, 1022, m