Theory of excluding induced subgraphs

Paul Seymour Department of Mathematics, Princeton University, Princeton, NJ, USA

Maria Chudnovsky, Columbia University, New York, NY, USA

2014/12/11 Thu 10:30AM-12PM, 1:30PM-3PM

2014/12/12 Fri 10:30AM-12PM, 1:30PM-3PM

E6-1, Room 1501

2014/12/12 Fri 10:30AM-12PM, 1:30PM-3PM

E6-1, Room 1501

This will be a series of four lectures, beginning with a general introduction to the area of induced subgraphs, and later focusing on several recent results. We will examine the structure of graphs that do not contain certain induced subgraphs, and in particular study relations between the clique number, stability number and chromatic number of these graphs. Later topics will include the strong perfect graph theorem, and recent progress on the Erdos-Hajnal conjecture, and on various conjectures of Gyárfás.