Topics in Discrete Mathematics: Induced Subgraphs

This course begins with a general introduction to the standard theorems about induced subgraphs, sketch the proof of the strong perfect graph theorem, and then go on to recent work on two famous conjectures (``H-free'' means not containing H as an induced subgraph):(i) The Erdos-Hajnal conjecture, that for every graph H, there exists c > 0 such that every H-free graph G 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 H-free graph with clique number at most k has chromatic number at most c.