Graph Colouring

Algorithm Engineering

a project of Jakub Marecek <jakub at marecek dot cz> (www)
and Dr. Andrew J. Parkes <ajp at cs dot nott dot ac dot uk> (www),
supervised by Prof. Edmund K. Burke <ekb at cs dot nott dot ac dot uk> (www).

An Overview

Graph colouring is a well-known problem in Graph Theory and Combinatorial Optimisation (www). We have tested several integer programming approaches to graph colouring and presented a new one, using a neat poly-time transformation of graph colouring to graph multicolouring, removing certain symmetries, making instances of linear programming smaller, and the search considerably faster. Especially for bounded graph colouring, however, the performance is still less than satisfactory, and hence we have been working on a branch and bound solver inspired by solvers for propositional satisfiability, not using any linear programming relaxations at all, or using subgradient methods to compute Lovasz Theta. We are also trying to study symmetry in benchmark instances for graph colouring empirically.

Outcomes

Zykov Revisited: Engineering an Solver for Graph Colouring
is in preparation. Preliminary version presented at:

• Zykov Revisited: Engineering an Solver for Graph Colouring,
  International Symposium on Combinatorial Optimization, CO 2008, Warwick University, UK, March 17—19, 2008 (abstract)
• Graph Colouring with Theta via the Spectral Bundle Method of Helmberg,
  Student Conference on Operations Research, SCOR 2009, Lancaster University Management School, UK, March 27-–29, 2009

Where is the Symmetry in Graph Colouring?
is in preparation. Preliminary version presented at:

• Where is the Symmetry in Graph Colouring?,
  International Symposium on Combinatorial Optimization, CO 2008, Warwick University, UK, March 17—19, 2008 (abstract)

Integer Programming Approaches to Vertex Colouring: A Computational Study
is in preparation

On a Clique-Based Integer Programming Formulation of Vertex Colouring with Applications in Course Timetabling,
has been submitted to a journal (pre-print also in arXiv, instances, BibTeX). Presented at:

• A Clique-Based Integer Programming Formulation of Graph Colouring and Applications,
  Seminar of the Centre for Discrete Mathematics and its Applications, DIMAP, Warwick University, UK, June 10, 2008 (slides)
• Integer Programming Formulations of Vertex Colouring,
  The Automated Scheduling, Optimisation and Planning Seminar, ASAP, Nottingham, UK, October 5, 2007 (slides)
• Variability of Integer Programming Models of Course Timetabling,
  European Conference on Operational Research, EURO XXII, Prague, CZ, July 8—11, 2007

Should you have any questions or comments, do not hesitate to contact Jakub <jakub at marecek dot cz>.

Go back to Jakub's homepage.