dimacs logo color

Events

Event Calendar

« Previous Month

August 2026

Next Month »
Sun Mon Tue Wed Thu Fri Sat
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

Seminar Details

Induced subgraphs and coloring

  • Start Date: June 11, 2019
  • Event Start Time: 2:00 PM
  • Event End Time: 3:00 PM
  • Organizers: Lazaros Gallos
  • Seminar Series: REU Seminar
  • Presenter(s): Maria Chudnovsky - Princeton University
  • Event Location: DIMACS Seminar room
  • 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 statement of the conjecture (now a theorem) is a structural description of all graphs that behave particularly well with respect to coloring in terms of their forbidden induced subgraphs. In the 1980s Andras Gyarfas made several beautiful conjectures, generalizing the idea of perfect graphs, by suggesting a more relaxed definition of what "behaving well" means. Recently, substantial progress has been made on these and other related questions, and we will discuss it in this talk. This is joint work with Alex Scott and Paul Seymour.