Seminars & Colloquia Calendar

Download as iCal file

Discrete Math

Induced cycles and coloring

Maria Chudnovsky: Princeton University

Location:  Hill 705
Date & time: Monday, 27 February 2017 at 2:00PM - 2:11PM

The Strong Perfect Graph Theorem states that graphs with no induced odd cycle of length at least five, and no complement of one behave very well with respect to coloring. But what happens if only some induced cycles (and no complements) are excluded? Gyarfas made three 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 the recent solutions of these conjectures.

This is joint work with Alex Scott, Paul Seymour and Sophie Spirkl.

Special Note to All Travelers

Directions: map and driving directions. If you need information on public transportation, you may want to check the New Jersey Transit page.

Unfortunately, cancellations do occur from time to time. Feel free to call our department: 848-445-6969 before embarking on your journey. Thank you.