Skip to main content
Princeton Mobile homeCourses home

Topics in Discrete Mathematics: Induced Subgraphs

MAT 579

Info tab content
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.
Instructors tab content
Sections tab content

Section C01