IEOR 8100 Graph Theory

Class Tue, Thu 11 -12:15, 317 Mudd

office hours Tue, 3-4, 308 Mudd

Course 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 will start with simple theorems about forbidden induced subgraphs, and work our way up to the latest research results. The topics will include perfect graphs, claw-free graphs, coloring graphs with forbidden induced subgraphs, algorithms for detecting induced subgraphs and others. Only basic knowledge of graph theory is required.

Grade determined by weekly/bi-weekly homework assignments