School of Computing Research Colloquia
- Date: Friday 8 March 2013, 13:00 – 14:00
- Location: Baines Wing
- Cost: £0
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.