The graph complement of a perfect graph is itself perfect. Originally known as the weak perfect graph conjecture (Fulkerson 1971), the result was subsequently proved by Lovász (1972) and thenceforth became known as the perfect graph theorem (Skiena 1990, p. 219; Cornuéjols 2002).

# Perfect Graph Theorem

## See also

Perfect Graph, Strong Perfect Graph Theorem## Explore with Wolfram|Alpha

## References

Cornuéjols, G. "The Strong Perfect Graph Conjecture."*International Congress of Mathematics, Beijing, China, 2002, Vol. 3.*pp. 547-559. http://integer.gsia.cmu.edu/webpub/SPGCsurvey.pdf.Fulkerson, D. R. "Blocking and Anti-Blocking Pairs of Polyhedra."

*Math. Program.*

**1**, 168-194, 1971.Lovász, L. "Normal Hypergraphs and the Perfect Graph Conjecture."

*Disc. Math.*

**2**, 253-267, 1972.Skiena, S.

*Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica.*Reading, MA: Addison-Wesley, 1990.West, D. B. "The Perfect Graph Theorem."

*Introduction to Graph Theory, 2nd ed.*Englewood Cliffs, NJ: Prentice-Hall, pp. 226 and 320-323, 2000.

## Referenced on Wolfram|Alpha

Perfect Graph Theorem## Cite this as:

Weisstein, Eric W. "Perfect Graph Theorem."
From *MathWorld*--A Wolfram Web Resource. https://mathworld.wolfram.com/PerfectGraphTheorem.html