June 30 – July 5 , 2019, Dagstuhl Seminar 19271

Graph Colouring: from Structure to Algorithms


Maria Chudnovsky (Princeton University, US)
Daniel Paulusma (Durham University, GB)
Oliver Schaudt (RWTH Aachen, DE)

For support, please contact

Dagstuhl Service Team


List of Participants
Shared Documents
Dagstuhl Seminar Wiki
Dagstuhl Seminar Schedule [pdf]

(Use seminar number and access code to log in)


The Graph Colouring problem is to label the vertices of a graph with the smallest possible number of colours in such a way that no two neighbouring vertices are identically coloured. Graph Colouring has been extensively studied in Computer Science and Mathematics due to its many application areas crossing disciplinary boundaries. Well-known applications of Graph Colouring include map colouring, job or timetable scheduling, register allocation, colliding data or traffic streams, frequency assignment and pattern matching. However, Graph Colouring is known to be computationally hard even if the number of available colours is limited to 3.

The aim of our seminar is to increase, in a systematic way, our understanding of the computational complexity of the Graph Colouring problem and related colouring problems. We plan to do this by determining to what extent the structure of a graph class plays a role in the tractability of the problem. For this purpose we bring together researchers from Discrete Mathematics and Theoretical Computer Science.

Topics of the seminar will include:

  • Hereditary Graph Classes
  • Width Parameters and Graph Decompositions
  • Certifying Algorithms
  • Parameterized Complexity
  • Generalizations of Graph Colouring

We plan an appropriate number of survey talks, presentations of recent results, open problem sessions, and ample time for discussions and problem solving. As concrete outcomes we expect to develop new general methodology and tools, which may have wider applicability, and to obtain new results reducing the gaps between the computationally hard and tractable cases of Graph Colouring and related problems, such as Precolouring Extension, List Colouring and H-Colouring.

Motivation text license
  Creative Commons BY 3.0 DE
  Maria Chudnovsky, Daniel Paulusma, and Oliver Schaudt


  • Data Structures / Algorithms / Complexity


  • (certifying / parameterized / polynomial-time) algorithms
  • Computational complexity
  • Graph colouring
  • Hereditary graph classes


In the series Dagstuhl Reports each Dagstuhl Seminar and Dagstuhl Perspectives Workshop is documented. The seminar organizers, in cooperation with the collector, prepare a report that includes contributions from the participants' talks together with a summary of the seminar.


Download overview leaflet (PDF).


Furthermore, a comprehensive peer-reviewed collection of research papers can be published in the series Dagstuhl Follow-Ups.

Dagstuhl's Impact

Please inform us when a publication was published as a result from your seminar. These publications are listed in the category Dagstuhl's Impact and are presented on a special shelf on the ground floor of the library.