Making Perfect Graphs
<-- Return to the list
Date: 09-11-2007
Start Time:
4:00pm
End Time: 5:00pm
Speaker: Paul Seymour, Princeton University
Location: 750 CEPSR
ABSTRACT
A graph is perfect if for every induced subgraph, its chromatic number is the same as the size of its largest clique. Th most well-known problem about perfect graphs, posed by Claude Berge in 1962, was the“strong perfect graph conjecture” (SPGC), that a graph is perfect if andonly if no induced subgraph is an odd cycle of length at least five, or the complement of one. This was proved in 2002 by Chudnovsky, Robertson, Thomas and myself, but a wider problem remained open; how how do you make the “most general” perfect graph? This remains open, and there doesnot see to be a plausible conjectured answer, even in the special case of three-colourable perfect graphs.
What the proof of the SPGC gives us is that either the graph belongs to one of several well-understood classes, or it admits one of several possibled ecompositions; and the problem is that one of these decompositions is notreversible, it does not yield a construction for perfect graphs. We would liketo avoid the use of this decomposition if we could, but so far there is no plausible substitute.
There is a half-way stage; not exactly a construction, but something better than what we have so far, a conjecture of Robin Thomas describing the structure of all perfect graphs without even pairs. (An even pair is apair of nonadjacent vertices such that every induced path joining them has even length.)
Studying this conjecture led us to two interesting things: first, that the last 50 or so pages of the proof of the SPGC could be replaced by something far simpler and shorter using even pairs; and second, that we can prove Thomas’ conjecture for three-colourable perfect graphs.
This is joint work with Dr. Maria Chudnovsky.
BIO
A bio for Dr. Paul Seymour can be found here.