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

Workshop Program:

All talks will be in rooms 214 and 224 of Fine Hall.

Thursday, May 7, 2009

 9:00 - 10:00  Survey on the Erdos-Hajnal conjecture
               Jacob Fox, Princeton University

10:00 - 10:30  Erdos-Hajnal conjecture, excluding 4-edge paths  and 5-edge antipaths
               Yori Zwols, Columbia University

11:00 - 12:00  Survey on Gyarfas' conjecture
               Alex Scott, Oxford

12:00 - 12:30  Gyarfas' conjecture: useful techniques and special cases
               Juraj Stacho, Paris

 5:00 -  5:30  Colouring circle graphs
               Sasha Kostochka, Illinois

 5:30          Problem session

Friday, May 8, 2009

 9:00 - 10:00  Minor-closed classes of binary matroids
               Bert Gerards, CWI, Amsterdam

10:30 - 11:30  Well-quasi-ordering binary matroids
               Jim Geelen, Waterloo

11:30 - 12:00  Excluded minors for bicircular matroids
               Matt Devos, Simon Fraser

 5:00 -  5:30  Fractional vs. integer colourings in clawfree graphs
               Andrew King, Montreal

 5:30 -  6:00  Approximate Hadwiger's conjecture for clawfree graphs
               Sasha Fradkin, Princeton

Saturday, May 9, 2009

 9:00 - 10:00  A survey on vertex-minors and pivot-minors
               Sang-Il Oum, KAIST, Korea

10:30 - 11:30  Graphs with no induced subdivisions of K4
               Frederic Maffray, Grenoble

11:30 - 12:00  An O(n+m) algorithm for split decomposition
               Pierre Charbit, Paris

 4:30 -  5:00  Total colouring 
               Bruce Reed, CNRS Sophia-Antipolis

 5:00 -  5:00  Colouring Berge graphs without balanced skew 
	       partitions and homogeneous pairs (structure theorem)
               Kristina Vuskovic, Leeds

 5:30 -  6:00  Colouring Berge graphs without balanced skew 
	       partitions and homogeneous pairs (colouring algorithm)
               Nicolas Trotignon, Paris

Sunday, May 10, 2009

 9:00 - 10:00  Large t-connected graphs excluding K_t
               Robin Thomas, Georgia Tech

10:30 - 11:00  Linking vortices
               Paul Wollan, Hamburg

11:00 - 11:30  3-connected projective-planar graphs
               Guoli Ding, Lousiana State

11:30 - 12:00  Spectral radius of planar graphs
               Bojan Mohar, Simon Fraser

 4:30 -  5:00  Edge-colouring via decomposition
               Raphael Machado, Rio de Janeiro

 5:00 -  5:30  Perfect matchings in cubic graphs
               Dan Kral, Prague

 6:00          Bus for banquet leaves from the Nassau Inn; returns at 12:00

Monday, May 11, 2009

  9:00 - 10:00 A new Caccetta-Haggkvist result
               Sergey Norin, Princeton

10:00 - 10:30  Paths and stable sets in digraphs
               Adrian Bondy, Lyon

11:00 - 11:30  Rao's conjecture and tournament wqo
               Maria Chudnovsky, Columbia

11:30 - 12:00  Topological containment in a tournament
               Paul Seymour, Princeton

Previous: Participation

Workshop Index

DIMACS Homepage