Recent progress on the Erdős-Hajnal conjecture
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.