Graph Colouring: from Structure to Algorithms

Summary

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.