https://www.dagstuhl.de/19271

June 30 – July 5 , 2019, Dagstuhl Seminar 19271

Graph Colouring: from Structure to Algorithms

Organizers

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

For support, please contact

Simone Schilke for administrative matters

Andreas Dolzmann for scientific matters

Motivation

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.

License
  Creative Commons BY 3.0 DE
  Maria Chudnovsky, Daniel Paulusma, and Oliver Schaudt

Classification

  • Data Structures / Algorithms / Complexity

Keywords

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

Book exhibition

Books from the participants of the current Seminar 

Book exhibition in the library, ground floor, during the seminar week.

Documentation

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).

Publications

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.

NSF young researcher support