### 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

Contacting the Center

Document last modified on January 12, 2006.