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 TheoremExplore 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 TheoremCite this as:
Weisstein, Eric W. "Perfect Graph Theorem." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/PerfectGraphTheorem.html