## Department Colloquium

### Friday, March 8th, 2019

**Time:** 2:30 p.m. **Place:** Jeffery Hall 234

**Speaker:** Maria Chudnovsky (Princeton University)

**Title:** Detecting odd holes.

**Abstract: ** A hole in a graph is an induced cycle of length at least four; and a hole is odd if it has an odd number of vertices. In 2003 a polynomial-time algorithm was found to test whether a graph or its complement contains an odd hole, thus providing a polynomial-time algorithm to test if a graph is perfect. However, the complexity of testing for odd holes (without accepting the complement outcome) remained unknown. This question was made even more tantalizing by a theorem of D. Bienstock that states that testing for the existence of an odd hole through a given vertex is NP-complete. Recently, in joint work with Alex Scott, Paul Seymour and Sophie Spirkl, we were able to design a polynomial time algorithm to test for odd holes. In this talk we will survey the history of the problem and the main ideas of the new algorithm.

**Prof. Chudnovsky (Princeton)** is a leading researcher in graph theory and combinatorics. She received her B.A. and M.Sc. form the Technion, and her PhD from Princeton University in 2003. Before returning to Princeton, she was a member of the IAS, a Clay Math. Inst. research fellow, and a Liu Family Professor of IEOR at Columbia University. For her joint work proving the strong perfect graph theorem, she was awarded the Ostrowski foundation research stipend in 2003 and the Fulkerson prize in 2009. In 2012, she was awarded the MacArthur Foundation Fellowship, and was an invited speaker at the 2014 ICM. Prof. Chudnovsky was also named one of the "brilliant ten" young scientists by the Popular Science magazine.