Editing Perfect graph (section)

==Algorithms==
In all perfect graphs, the [[graph coloring problem]], [[maximum clique problem]], and [[maximum independent set problem]] can all be solved in [[polynomial time]]. The algorithm for the general case involves the [[Lovász number]] of these graphs. The Lovász number of any graph can be determined by labeling its vertices by high dimensional [[unit vector]]s, so that each two non-adjacent vertices have perpendicular labels, and so that all of the vectors lie in a cone with as small an opening angle as possible. Then, the Lovász number is <math>1/\cos^2\theta</math>, where <math>\theta</math> is the half-angle of this cone. Despite this complicated definition, an accurate numerical value of the Lovász number can be computed using [[semidefinite programming]], and for any graph the Lovász number is sandwiched between the chromatic number and clique number. Because these two numbers equal each other in perfect graphs, they also equal the Lovász number. Thus, they can be computed by approximating the Lovász number accurately enough and rounding the result to the nearest integer.{{r|gls-1984|gls-1988}}

The solution method for semidefinite programs, used by this algorithm, is based on the [[ellipsoid method]] for [[linear programming]]. It leads to a polynomial time algorithm for computing the chromatic number and clique number in perfect graphs. However, solving these problems using the Lovász number and the ellipsoid method is complicated and has a high polynomial exponent.{{r|gls-1984|gls-1988}} More efficient combinatorial algorithms are known for many special cases.{{r|golumbic-1980}}

This method can also be generalized to find the maximum weight of a clique, in a weighted graph, instead of the clique number. A maximum or maximum weight clique itself, and an optimal coloring of the graph, can also be found by these methods, and a maximum independent set can be found by applying the same approach to the complement of the graph. For instance, a maximum clique can be found by the following algorithm:{{r|gls-1984}}
*Loop through the vertices of the graph. For each vertex <math>v</math>, perform the following steps:
**Tentatively remove <math>v</math> from the graph.
**Use semidefinite programming to determine the clique number of the resulting induced subgraph.
**If this clique number is the same as for the whole graph, permanently remove <math>v</math>; otherwise, restore <math>v</math> to the graph.
*Return the subgraph that remains after all the permanent removals.
The algorithm for finding an optimal coloring is more complicated, and depends on the duality theory of linear programs, using this clique-finding algorithm as a [[separation oracle]].{{r|gls-1984}}

Beyond solving these problems, another important computational problem concerning perfect graphs is their recognition, the problem of testing whether a given graph is perfect. For many years the complexity of recognizing Berge graphs and perfect graphs were considered separately (as they were not yet known to be equivalent) and both remained open. They were both known to be in [[co-NP]]; for Berge graphs, this follows from the definition,{{r|lovasz-1983}} while for perfect graphs it follows from the characterization using the product of the clique number and independence number.{{r|gasparyan}} After the strong perfect graph theorem was proved, Chudnovsky, Cornuéjols, Liu, Seymour, and Vušković discovered a polynomial time algorithm for testing the existence of odd holes or anti-holes. By the strong perfect graph theorem, this can be used to test whether a given graph is perfect, in polynomial time.{{r|cclsv-2005}}