Perfect graph

Perfect graph
The Paley graph of order 9, colored with three colors and showing a clique of three vertices. In this graph and each of its induced subgraphs the chromatic number equals the clique number, so it is a perfect graph.

In graph theory, a perfect graph is a graph in which the chromatic number of every induced subgraph equals the size of the largest clique 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 (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

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
  • trapezoid 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)
  • trivially perfect graphs (in every induced subgraph the size of the largest independent set equals the number of maximal cliques)
  • 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)
  • 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 was a longstanding open problem. 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.)

References

External links


Wikimedia Foundation. 2010.

Игры ⚽ Поможем написать реферат

Look at other dictionaries:

  • Perfect (disambiguation) — Perfect may refer to: * Perfection, a philosophical concept * Perfection (law), a legal concept * Perfect aspect, a grammatical concept * Perfect, a Cathar priestIn mathematics: * Perfect number * Perfect group * Perfect set * Perfect graphIn… …   Wikipedia

  • Graph coloring — A proper vertex coloring of the Petersen graph with 3 colors, the minimum number possible. In graph theory, graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called colors to elements of a graph… …   Wikipedia

  • Graph theory — In mathematics and computer science, graph theory is the study of graphs : mathematical structures used to model pairwise relations between objects from a certain collection. A graph in this context refers to a collection of vertices or nodes and …   Wikipedia

  • perfect forecast line — Graph of a slope that matches the forecast of an exchange rate with the actual exchange rate. Bloomberg Financial Dictionary …   Financial and business terms

  • Graph factorization — Not to be confused with Factor graph. 1 factorization of Desargues graph: each color class is a 1 factor …   Wikipedia

  • Graph (mathematics) — This article is about sets of vertices connected by edges. For graphs of mathematical functions, see Graph of a function. For statistical graphs, see Chart. Further information: Graph theory A drawing of a labeled graph on 6 vertices and 7 edges …   Wikipedia

  • Graph operations — Operations on graphs produce new graphs from old ones. They may be separated into the following major categories. Contents 1 Unary operations 1.1 Elementary operations 1.2 Advanced operations 2 …   Wikipedia

  • Claw-free graph — A claw In graph theory, an area of mathematics, a claw free graph is a graph that does not have a claw as an induced subgraph. A claw is another name for the complete bipartite graph K1,3 (that is, a star graph with three edges, three leaves, and …   Wikipedia

  • König's theorem (graph theory) — In the mathematical area of graph theory, König s theorem describes an equivalence between the maximum matching problem and the minimum vertex cover problem in bipartite graphs. Setting A graph is bipartite if its vertices can be partitioned into …   Wikipedia

  • Distance-hereditary graph — A distance hereditary graph. In graph theoretic mathematics, a distance hereditary graph (also called a completely separable graph)[1] is a graph in which the distances in any connected induced subgraph are the same as they are in the original… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”