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 Roberston, 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.
Penn Mathematics Colloquium
Wednesday, September 25, 2013 - 4:30pm
Maria Chudnovsky
Columbia University