The strong perfect graph conjecture -- Allison Gilmore
<p>

The strong perfect graph conjecture was an open problem in graph theory for nearly 40
years.  A perfect graph is one for which the chromatic number of every induced subgraph
equals the size of its largest clique.  The conjecture claimed that a graph is perfect if
and only if it contains no odd holes or anti-holes.  It was proved in 2002 by a team of
mathematicians.  In this talk, I will introduce the terminology necessary to understand
the conjecture, give some idea of how it was proved, and describe other interesting
classes of graphs that can be characterized in terms of their induced subgraphs.  No
background knowledge of graph theory required; the talk should be accessible to anybody!