Topics in Discrete Mathematics: Induced Subgraphs

This course begins with a general introduction to the standard theorems about induced subgraphs, then go on to survey some recent work. Two central conjectures are (i) the Erdos-Hajnal conjecture, that every graph H, there exists c>0 such that every graph G not containing H as an induced subgraph has a clique or stable set of size at least |G|^c, and (ii) the Gyarfas-Sumner conjecture, that for every tree H and every integer k, there exists c such that every graph not containing H as an induced subgraph and with clique number at most k, has chromatic number at most c. Attempts to prove these two conjectures are themes throughout.