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
Documents
Dagstuhl Seminar Schedule (Upload here)
(Use seminar number and access code to log in)
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