Plücker Lecture by Maria Chudnovsky

Maria Chudnovsky
Princeton University

Title: Perfection and Beyond

Date: December 5, 2016, 17:00 to 18:00

The BIGS Party will take place after the lecture in the Hausdorff and Plücker-Rooms.

Venue: Lipschitz-Hall, Endenicher Allee 60

Abstract:

About 10 years ago one of the central open problems in graph theory at the time, the Strong Perfect Graph Conjecture, was solved. The proof used structural graph theory methods, and spanned 155 journal pages. The speaker was part of the team of authors of this mathematical beast. In this talk we will explain the problem, describe some of the ideas of the proof (that has since been shortened somewhat), and discuss exciting related problems that have been a subject of more recent research.

Title: Induced subgraphs and coloring

Date: December 6, 2016, 18:00 to 19:00

Coffee and tea will be served before the lecture.

Venue: Lipschitz-Hall, Endenicher Allee 60

 Abstract:

The Strong Perfect Graph Theorem states that graphs with no induced odd cycle of length at least five, and no complements of one behave very well with respect to coloring. But what happens if only some induced cycles (and no complements) are excluded? Gyarfas made a number of conjectures on this topic, asserting that in many cases the chromatic number is bounded by a function of the clique number. In this talk we discuss recent progress on some of these conjectures, and related questions.

This is joint work with Alex Scott and Paul Seymour.