Perfect Graph Theorem

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

See also

Perfect Graph, Strong Perfect Graph Theorem

Explore with Wolfram|Alpha


Cornuéjols, G. "The Strong Perfect Graph Conjecture." International Congress of Mathematics, Beijing, China, 2002, Vol. 3. pp. 547-559., 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.

Subject classifications