Siani Smith

Acyclic, Star and Injective Colouring: Complexity for H-free Graphs

We study the computational complexity of three variants of the colouring problem, acyclic, star and injective colouring. Almost complete complexity dichotomies are obtained for each problem, both in the case where the number of colours is fixed and where it is part of the input. This is joint work with Jan Bok, Nikola Jedlickova, Barnaby Martin, Pascal Ochem and Daniel Paulusma.