Recent progress on the Erdős-Hajnal conjecture


Professor Maria Chudnovsky (Princeton University)
Thu January 30th 2020, 4:30pm
Bldg 380 Room 380W

What is the effect of excluding an induced subgraph on the global structure of a graph?  While there do not seem to be general structural consequences, a conjecture of Erdős and Hajnal says that graphs with forbidden induced subgraphs behave very differently from general graphs; more
precisely, they contain much larger cliques or stable sets.  This conjecture is still open.  In this talk we will discuss the history of this problem and some recent theorems related to it.

You can learn more about Professor Maria Chudnovsky at