Dagstuhl Seminar 19271
Graph Colouring: from Structure to Algorithms
( Jun 30 – Jul 05, 2019 )
(Click in the middle of the image to enlarge)
Permalink
Please use the following short url to reference this page:
https://www.dagstuhl.de/19271
Organizers
- Maria Chudnovsky (Princeton University, US)
- Daniel Paulusma (Durham University, GB)
- Oliver Schaudt (RWTH Aachen, DE)
Contact
- Andreas Dolzmann (for scientific matters)
Dagstuhl Seminar Wiki
- Dagstuhl Seminar Wiki (Use personal credentials as created in DOOR to log in)
Shared Documents
- Dagstuhl Materials Page (Use personal credentials as created in DOOR to log in)
Impacts
- Finding large H-colorable subgraphs in hereditary graph classes: article - Chudnovsky, Maria; King, Jason; Pilipczuk, Michal; Rzazewski, Pawel; Spirkl, Sophie - Cornell University : arXiv.org, 2020. - 29 pp..
- On Weak Flexibility in Planar Graphs - Lidicky, Bernard; Masarík, Tomas; Murphy, Kyle; Zerbib, Shira - Cornell University : arXiv.org, 2020. - 15 pp..
Schedule
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.
Creative Commons BY 3.0 DE
Maria Chudnovsky, Daniel Paulusma, and Oliver Schaudt
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 central research aim of our seminar was to increase our understanding of the computational complexity of the Graph Colouring problem and related NP-complete colouring problems, such as Precolouring Extension, List Colouring and $H$-Colouring. The approach followed at the seminar for achieving this aim was to restrict the input of a colouring problem to some special graph class and to determine wether such a restriction could make the problem tractable.
As input restriction, the main focus was to consider hereditary graph classes, which are those classes of graphs that are closed under vertex deletion. Hereditary graph classes provide a unified framework for a large collection of well-known graph classes. The reason for this is that a graph class is hereditary if and only if it can be characterized by a (unique) set H of minimal forbidden induced subgraphs. This property enables a systematic study into the computational complexity of a graph problem under input restrictions. For instance, one can first restrict the input to some hereditary graph class for which H is small, say cal H has size 1 or 2, or for which H consists of small graphs only.
In line with the seminar's research aim, the seminar brought together researchers from Discrete Mathematics, working in structural graph theory, and researchers from Theoretical Computer Science, working in algorithmic graph theory. In total, 45 participants participated from 14 different countries.
The scientific program of the seminar consisted of 23 sessions: 4 one-hour survey talks, 17 contributed talks of at most thirty minutes and 2 open problem sessions. This left ample time for discussions and problem solving.
Each of the four survey talks covered a particular structural or algorithmic key aspect of the seminar to enable collaborations of researchers with different backgrounds. On Monday, Sophie Sprikl presented a state-of-the-art summary of the Graph Colouring problem for H-free graphs and gave the main ideas and techniques behind an important, recent result in the area, namely a polynomial-time algorithm for colouring P_6-free graphs with at most four colours. On Tuesday, Marcin Pilipczuk gave a tutorial on the framework of minimal chordal completions and potential maximal cliques. This technique plays a crucial role for solving the Maximum Independent Set problem on some hereditary graph classes, but has a much wider applicability. On Wednesday, Bart Jansen gave a presentation on the parameterized complexity of the Graph Colouring problem and related colouring problems. Due to a large variety of possible parameterizatons, Jansen's talk covered a wide range of open problems. On Thursday, Konrad Dabrowski gave an introduction to the clique-width of hereditary graph classes. If a graph class has bounded clique-width, then Graph Colouring and many other NP-hard problems become polynomial-time solvable. Hence, as a first step in the design of a polynomial-time algorithm, one may first want to verify if the clique-width (or any equivalent width parameter) of the graph class under consideration is bounded.
The two general open problem sessions took place on Monday and Tuesday afternoon. Details of the presented problems can be found in the report, together with abstracts of all the talks.
Maria Chudnovsky, Daniel Paulusma, and Oliver Schaudt
- Isolde Adler (University of Leeds, GB) [dblp]
- Marthe Bonamy (University of Bordeaux, FR) [dblp]
- Nicolas Bousquet (Grenoble INP, FR) [dblp]
- Christoph Brause (TU Bergakademie Freiberg, DE) [dblp]
- Kathie Cameron (Wilfrid Laurier University - Waterloo, CA) [dblp]
- Maria Chudnovsky (Princeton University, US) [dblp]
- Konrad Dabrowski (Durham University, GB) [dblp]
- Cemil Dibek (Princeton University, US) [dblp]
- Francois Dross (University of Montpellier & CNRS, FR) [dblp]
- Esther Galby (University of Fribourg, CH) [dblp]
- Petr A. Golovach (University of Bergen, NO) [dblp]
- Chinh T. Hoàng (Wilfrid Laurier University - Waterloo, CA) [dblp]
- Shenwei Huang (Nankai University - Tianjin, CN) [dblp]
- Bart Jansen (TU Eindhoven, NL) [dblp]
- Matthew Johnson (Durham University, GB) [dblp]
- Mamadou Moustapha Kanté (Université Clermont Auvergne - Aubiere, FR) [dblp]
- Tereza Klimosova (Charles University - Prague, CZ) [dblp]
- Stefan Kratsch (HU Berlin, DE) [dblp]
- O-joung Kwon (Incheon National University, KR) [dblp]
- Bernard Lidicky (Iowa State University, US) [dblp]
- Anita Liebenau (UNSW Sydney, AU) [dblp]
- Paloma Lima (University of Bergen, NO) [dblp]
- Daniel Lokshtanov (University of California - Santa Barbara, US) [dblp]
- Peter Maceli (Adelphi University - Garden City, US) [dblp]
- Tomas Masarik (Charles University - Prague, CZ) [dblp]
- Sang-il Oum (IBS - Daejeon, KR) [dblp]
- Daniel Paulusma (Durham University, GB) [dblp]
- Irena Penev (Charles University - Prague, CZ) [dblp]
- Marcin Pilipczuk (University of Warsaw, PL) [dblp]
- Michal Pilipczuk (University of Warsaw, PL) [dblp]
- Bernard Ries (University of Fribourg, CH) [dblp]
- Pawel Rzazewski (Warsaw University of Technology, PL) [dblp]
- Oliver Schaudt (RWTH Aachen, DE) [dblp]
- Ingo Schiermeyer (TU Bergakademie Freiberg, DE) [dblp]
- Pascal Schweitzer (TU Kaiserslautern, DE) [dblp]
- Paul Seymour (Princeton University, US) [dblp]
- Sophie Spirkl (Rutgers University - Piscataway, US) [dblp]
- Juraj Stacho (Google Switzerland - Zürich, CH) [dblp]
- Maya Stein (University of Chile - Santiago de Chile, CL) [dblp]
- Stéphan Thomassé (ENS - Lyon, FR) [dblp]
- Nicolas Trotignon (ENS - Lyon, FR) [dblp]
- Zsolt Tuza (Alfréd Rényi Institute of Mathematics - Budapest, HU) [dblp]
- Erik Jan van Leeuwen (Utrecht University, NL) [dblp]
- Gerhard J. Woeginger (RWTH Aachen, DE) [dblp]
- Viktor Zamaraev (Durham University, GB) [dblp]
Related Seminars
Classification
- data structures / algorithms / complexity
Keywords
- (certifying / parameterized / polynomial-time) algorithms
- computational complexity
- graph colouring
- hereditary graph classes
