Editing Perfect graph (section)

== History ==
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 graph|complement]] of a [[bipartite graph]] is perfect;{{r|gallai-1958}} this result can also be viewed as a simple equivalent of [[Kőnig's theorem (graph theory)|Kőnig's theorem]], a much earlier result relating matchings and vertex covers in bipartite graphs. The first formulation of the concept of perfect graphs more generally was in a 1961 paper by [[Claude Berge]], in German,{{r|berge-1961}} and the first use of the phrase "perfect graph" appears to be in a 1963 paper of Berge.{{r|berge-1963}} In these works he unified Gallai's result with several similar results by defining perfect graphs, and he conjectured both the perfect graph theorem and the strong perfect graph theorem. In formulating these concepts, Berge was motivated by the concept of the [[Shannon capacity of a graph]], by the fact that for (co-)perfect graphs it equals the independence number, and by the search for minimal examples of graphs for which this is not the case.<ref>{{harvtxt|Chudnovsky|Robertson|Seymour|Thomas|2003}}; note that Chudnovsky et al define capacity using the complement of the graphs used for the definition in [[Shannon capacity of a graph]], and include a logarithm that the linked article does not include.</ref> Until the strong perfect graph theorem was proven, the graphs described by it (that is, the graphs with no odd hole and no odd antihole) were called ''Berge graphs''.{{r|hougardy-2006}}

The perfect graph theorem was proven by [[László Lovász]] in 1972,{{r|lovasz-1972a}} who in the same year proved the stronger inequality between the number of vertices and the product of the clique number and independence number, without benefit of the strong perfect graph theorem.{{r|lovasz-1972b}} In 1991, Alfred Lehman won the [[Fulkerson Prize]], sponsored jointly by the [[Mathematical Optimization Society]] and [[American Mathematical Society]], for his work on generalizations of the theory of perfect graphs to [[logical matrix|logical matrices]].{{r|fulkerson-prize-1991}} The conjectured strong perfect graph theorem became the focus of research in the theory of perfect graphs for many years,{{r|hougardy-2006}} until its proof was announced in 2002 by [[Maria Chudnovsky]], [[Neil Robertson (mathematician)|Neil Robertson]], [[Paul Seymour (mathematician)|Paul Seymour]], and [[Robin Thomas (mathematician)|Robin Thomas]],{{r|mackenzie-2002}} and published by them in 2006.{{r|crst-2006}} This work won its authors the 2009 Fulkerson Prize.{{r|fulkerson-prize-2009}} The perfect graph theorem has a short proof,{{r|lovasz-1972b|gasparyan}} but the proof of the strong perfect graph theorem is long and technical, based on a deep structural decomposition of Berge graphs. Related decomposition techniques have also borne fruit in the study of other graph classes, and in particular for the [[claw-free graph]]s.{{r|cs-2005}} The symmetric characterization of perfect graphs in terms of the product of clique number and independence number was originally suggested by [[András Hajnal|Hajnal]] and proven by Lovász.{{r|lovasz-1972b}}