 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

 WHAT'S NEW

SEARCH ALL

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.

 (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 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
Press Releases | Feeds | Contact