https://www.dagstuhl.de/19271

30. Juni – 05. Juli 2019, Dagstuhl Seminar 19271

Graph Colouring: from Structure to Algorithms

Organisatoren

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

Auskunft zu diesem Dagstuhl Seminar erteilen

Simone Schilke zu administrativen Fragen

Andreas Dolzmann zu wissenschaftlichen Fragen

Dokumente

Programm des Dagstuhl Seminars (Hochladen)

(Zum Einloggen bitte Seminarnummer und Zugangscode verwenden)

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

Buchausstellung

Bücher der Teilnehmer 

Buchausstellung im Erdgeschoss der Bibliothek

(nur in der Veranstaltungswoche).

Dokumentation

In der Reihe Dagstuhl Reports werden alle Dagstuhl-Seminare und Dagstuhl-Perspektiven-Workshops dokumentiert. Die Organisatoren stellen zusammen mit dem Collector des Seminars einen Bericht zusammen, der die Beiträge der Autoren zusammenfasst und um eine Zusammenfassung ergänzt.

 

Download Übersichtsflyer (PDF).

Publikationen

Es besteht weiterhin die Möglichkeit, eine umfassende Kollektion begutachteter Arbeiten in der Reihe Dagstuhl Follow-Ups zu publizieren.

Dagstuhl's Impact

Bitte informieren Sie uns, wenn eine Veröffentlichung ausgehend von
Ihrem Seminar entsteht. Derartige Veröffentlichungen werden von uns in der Rubrik Dagstuhl's Impact separat aufgelistet  und im Erdgeschoss der Bibliothek präsentiert.