DIMACS Workshop on Graph Colouring and Structure

May 7 - 11, 2009
Princeton University

Organizers:

Maria Chudnovsky, Columbia University, mchudnov at columbia.edu

Paul Seymour, Princeton University, pds at Math.Princeton.EDU

Robin Thomas, Georgia Tech, thomas at math.gatech.edu

The workshop is on graph colouring, graph structure and induced subgraphs, and will focus on the intersections of these topics. Some central problems in this area are:

(a) is there a combinatorial algorithm to optimally colour a perfect graph
in polynomial time?

(b) Gyarfas' conjecture that for any fixed tree T, the graphs not containing
T as an induced subgraph have chromatic number bounded by a function of
their clique number

(c) the conjecture that the same is true for graphs with no odd hole

(d) the Erdos-Hajnal conjecture, that for any fixed graph H, all graphs not
containing H as an induced subgraph have either a clique or a stable set of
size polynomial in the size of the graph

(e) what is the structure of perfect graphs without even pairs?

(f) the structure of balanced graphs?

(g) which of Cornuejols' $5000 problems should be attacked next?

We would like to devote about half of the time to lectures and the other half to working together and solving all these problems.

Next: Call for Participation

Workshop Index

DIMACS Homepage