You are here

Perfection and Beyond

About ten years ago the Strong Perfect Graph Conjecture, a well-known problem in both graph theory and combinatorial optimization, was proved (this result is due to the speaker, in joint work with Robertson, Seymour and Thomas). The proof used methods from structural graph theory. The original version of the proof spanned about 150 journal pages, but it has since been somewhat shortened. In this talk we will describe the problem, explain its importance, outline some of the ideas underlying the proof, and also discuss related problems that have been the subject of recent research.