School of Computing Research Colloquia

Colouring asteriodal-triple-free graphs

Haiko Muller, Algorithms and Complexity Research Group

Colourings are one of the classical subjects in graph theory. Algorithmically it is hard to decide whether the vertices of a given graph can be coloured by k available colours, such that adjacent vertices receive different colours. More precisely, the corresponding decision problem is NP-complete, even for fixed k>2. Therefore we are interested in the computational complexity of the vertex colouring problem when restricted to graph in special classes. For many classes the complexity status is known. A prominent example are perfect graphs, for which the vertex colouring problem is solvable in polynomial time.

Three vertices form an asteroidal triple if between any two of them there is a path avoiding all neighbours of the third one. Graphs without asteroidal triples are AT-free. All interval graphs are AT-free, and the class of AT-free graphs is incomparable with the class of perfect graphs. The complexity of the vertex colouring problem restricted to AT-free graphs is not known. We present the first polynomial time algorithm for the case that the number of available colours is fixed.