Department of Mathematics  
Seminars  
Address: Mathematics
25337

Caltech

Pasadena,
CA 91125
Telephone: (626) 3954335  Fax: (626) 5851728 
Project MATHEMATICS!  Caltech Home 
Mathematics
Colloquium
2013  2014 
Friday,
January
24,
2014 3:00 p.m. // 151 Sloan Maria Chudnovsky (Columbia)  Perfection and Beyond Abstract: About ten years ago the Strong Perfect Graph Conjecture, a wellknown 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. 
