Robin Thomas wins his second D. Ray Fulkerson Prize

Robin Thomas received the 2009 D. Ray Fulkerson Prize on August 23rd at the 20th International Symposium on Mathematical Programming alongside colleagues Maria Chudnovsky of Columbia University, Neil Robertson of the Ohio State University, and Paul Seymour of Princeton University. The research team's paper "The Strong Perfect Graph Theorem," published in the Annals of Mathematics in 2006, resolves a conjecture proposed in 1960 by Claude Berge, one of the modern founders of combinatorics and graph theory.

The citation states that Claude Berge introduced the class of perfect graphs in 1960 together with a possible characterization in terms of forbidden subgraphs. The resolution of Berge's strong perfect graph conjecture quickly became one of the most sought after goals in graph theory. The pursuit of the conjecture brought together four important elements: vertex colorings, stable sets, cliques, and clique covers. Moreover, D. R. Fulkerson established connections between perfect graphs and integer programming through his theory of anti-blocking polyhedra. A graph is called perfect if for every induced subgraph H the clique-covering number of H is equal to the cardinality of its largest stable set. The strong perfect graph conjecture states that a graph is perfect if and only if neither it nor its complement contains as an induced subgraph an odd circuit having at least five edges. The elegance and simplicity of this possible characterization led to a great body of work in the literature, culminating in the proof by Chudnovsky, Robertson, Seymour and Thomas, announced in May 2002, just one month before Berge passed away. The long, difficult, and creative proof by Chudnovsky et al. is one of the great achievements in discrete mathematics.