Perfect graph
In graph theory
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 a collection of edges that connect pairs of...

, a perfect graph is a graph
Graph (mathematics)
In mathematics, a graph is an abstract representation of a set of objects where some pairs of the objects are connected by links. The interconnected objects are represented by mathematical abstractions called vertices, and the links that connect some pairs of vertices are called edges...

 in which the chromatic number
Graph coloring
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 subject to certain constraints. In its simplest form, it is a way of coloring the vertices of a graph such that no two adjacent vertices share the...

 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 . In addition, several important min-max theorems in combinatorics
Combinatorics is a branch of mathematics concerning the study of finite or countable discrete structures. Aspects of combinatorics include counting the structures of a given kind and size , deciding when certain criteria can be met, and constructing and analyzing objects meeting the criteria ,...

, such as Dilworth's theorem
Dilworth's theorem
In mathematics, in the areas of order theory and combinatorics, Dilworth's theorem characterizes the width of any finite partially ordered set in terms of a partition of the order into a minimum number of chains...

, 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
Tibor Gallai
Tibor Gallai was a Hungarian mathematician. He worked in combinatorics, especially in graph theory, and was a lifelong friend and collaborator of Paul Erdős. He was a student of Dénes König and an advisor of László Lovász...

 that in modern language can be interpreted as stating that the complement
Complement graph
In graph theory, the complement or inverse of a graph G is a graph H on the same vertices such that two vertices of H are adjacent if and only if they are not adjacent in G. That is, to generate the complement of a graph, one fills in all the missing edges required to form a complete graph, and...

 of a bipartite graph
Bipartite graph
In the mathematical field of graph theory, a bipartite graph is a graph whose vertices can be divided into two disjoint sets U and V such that every edge connects a vertex in U to one in V; that is, U and V are independent sets...

 is perfect; this result can also be viewed as a simple equivalent of König's theorem
König's theorem (graph theory)
In the mathematical area of graph theory, König's theorem, proved by Dénes Kőnig in 1931, describes an equivalence between the maximum matching problem and the minimum vertex cover problem in bipartite graphs...

, 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
Claude Berge
Claude Berge was a French mathematician, recognized as one of the modern founders of combinatorics and graph theory. He is particularly remembered for his famous conjectures on perfect graphs and for Berge's lemma, which states that a matching M in a graph G is maximum if and only if there is in...

. 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 graph
    Bipartite graph
    In the mathematical field of graph theory, a bipartite graph is a graph whose vertices can be divided into two disjoint sets U and V such that every edge connects a vertex in U to one in V; that is, U and V are independent sets...

  • The line graph
    Line graph
    In graph theory, the line graph L of undirected graph G is another graph L that represents the adjacencies between edges of G...

    s of bipartite graphs (see König's theorem
    König's theorem (graph theory)
    In the mathematical area of graph theory, König's theorem, proved by Dénes Kőnig in 1931, describes an equivalence between the maximum matching problem and the minimum vertex cover problem in bipartite graphs...

  • interval graph
    Interval graph
    In graph theory, an interval graph is the intersection graph of a multiset of intervals on the real line. It has one vertex for each interval in the set, and an edge between every pair of vertices corresponding to intervals that intersect.-Definition:...

    s (vertices represent line intervals; and edges, their pairwise nonempty intersections)
  • chordal graph
    Chordal graph
    In the mathematical area of graph theory, a graph is chordal if each of its cycles of four or more nodes has a chord, which is an edge joining two nodes that are not adjacent in the cycle. An equivalent definition is that any chordless cycles have at most three nodes...

    s (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 graph
    Distance-hereditary graph
    In graph-theoretic mathematics, a distance-hereditary graph is a graph in which the distances in any connected induced subgraph are the same as they are in the original graph...

  • permutation graph
    Permutation graph
    In areas of mathematics influenced by graph theory, a permutation graph is the intersection graph of a family of line segments that connect two parallel lines in the Euclidean plane...

  • trapezoid graph
    Trapezoid graph
    In graph theory, trapezoid graphs are intersection graphs of trapezoids between two horizontal lines. They are a class of co-comparability graphs that contain interval graphs and permutation graphs as subclasses...

  • comparability graph
    Comparability graph
    In graph theory, a comparability graph is an undirected graph that connects pairs of elements that are comparable to each other in a partial order...

    s (a vertex per element in a partial order, and an edge between any two comparable elements)
  • wheel graph
    Wheel graph
    In the mathematical discipline of graph theory, a wheel graph Wn is a graph with n vertices, formed by connecting a single vertex to all vertices of an -cycle. The numerical notation for wheels is used inconsistently in the literature: some authors instead use n to refer to the length of the cycle,...

    s with an odd number of vertices
  • split graph
    Split graph
    In graph theory, a branch of mathematics, a split graph is a graph in which the vertices can be partitioned into a clique and an independent set...

    s (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
    Greedy coloring
    In the study of graph coloring problems in mathematics and computer science, a greedy coloring is a coloring of the vertices of a graph formed by a greedy algorithm that considers the vertices of the graph in sequence and assigns each vertex its first available color...

     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
Lovász :* Lázár Lovász , a Hungarian athlete who competed in hammer throw* László Lovász , a mathematician, best known for his work in combinatorics,** Lovász conjecture ** Erdős–Faber–Lovász conjecture...

A graph is perfect if and only if
If and only if
In logic and related fields such as mathematics and philosophy, if and only if is a biconditional logical connective between statements....

 its complement
Glossary of graph theory
Graph theory is a growing area in mathematical research, and has a large specialized vocabulary. Some authors use the same word with different meanings. Some authors use different words to mean the same thing. This page attempts to keep up with current usage....

 is perfect.

An induced cycle
Induced path
In the mathematical area of graph theory, an induced path in an undirected graph G is a path that is an induced subgraph of G. That is, it is a sequence of vertices in G such that each two adjacent vertices in the sequence are connected by an edge in G, and each two nonadjacent vertices in the...

 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
Maria Chudnovsky
Maria Chudnovsky is an Israeli mathematician. She is professor in the departments of mathematics and of industrial engineering and operations research at Columbia University. She grew up in Russia and Israel, studying at the Technion, and received her Ph.D. in 2003 from Princeton University under...

, Robertson
Neil Robertson (mathematician)
G. Neil Robertson is a mathematician working mainly in topological graph theory, currently a distinguished professor at the Ohio State University. He earned his Ph.D. in 1969 at the University of Waterloo under his doctoral advisor William Tutte. According to the criteria of the Erdős Number...

, Seymour, Thomas
Robin Thomas (mathematician)
Robin Thomas is a mathematician working in graph theory at the Georgia Institute of Technology.Thomas received his doctorate in 1985 from Charles University in Prague, Czechoslovakia , under the supervision of Jaroslav Nešetřil...

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
P (complexity)
In computational complexity theory, P, also known as PTIME or DTIME, is one of the most fundamental complexity classes. It contains all decision problems which can be solved by a deterministic Turing machine using a polynomial amount of computation time, or polynomial time.Cobham's thesis holds...

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

External links

The source of this article is wikipedia, the free encyclopedia.  The text of this article is licensed under the GFDL.