Problem of the Week
Hilton Memorial Lecture
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 Erdos and Hajnal states 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. I will discuss the history of this problem and some recent theorems related to it.