Topics in Discrete Mathematics: Induced Subgraphs

Subject associations
MAT 579
Term
Fall 2020
Instructors
Paul Seymour
Registrar description

This is a general introduction to the topic of induced subgraphs. We will assume knowledge of basic graph theory, but nothing more. We will survey some of the main theorems (perfect graph theorem, chi-boundedness results, claw-free graphs), and then focus on several open questions:the Erdos-Hajnal conjecture, the Conlon-Fox-Sudakov conjecture, the Gyarfas-Sumner conjecture, and the Liebenau-Pilipczuk conjecture (recently proved).These are all conjectures that say that with certain types of induced subgraph excluded, certain nice things happen.