Topics in Discrete Mathematics: Forbidding Induced Subgraphs: Structure and Properties

Subject associations
MAT 579
Term
Spring 2026
Instructors
Maria Chudnovsky
Registrar description

The study of the structure of graphs with certain induced subgraphs forbidden has been an active area of research in graph theory in recent years, after the long standing Strong Perfect Graph Conjecture was proved using structural methods. The goal of this course is to cover some of the recent developments in the area. We start with simple theorems about forbidden induced subgraphs, and work our way up to the latest research results. The topics include perfect graphs, claw-free graphs, coloring graphs with forbidden induced subgraphs, algorithms for detecting induced subgraphs and others.