Abstract: We study the computational complexity of computing role colourings of graphs in hereditary classes. We are interested in describing the family of hereditary classes on which a role colouring with k colours can be computed in polynomial time. In particular, we wish to describe the boundary between the “hard” and “easy” classes. The notion of a boundary class has been introduced by Alekseev in order to study such boundaries. Our main results are a boundary class for the k-role colouring problem and the related k-coupon colouring problem which has recently received a lot of attention in the literature. The latter result makes use of a technique for generating regular graphs of arbitrary girth which may be of independent interest.
Abstract: We prove several results about the complexity of the role colouring problem. A role colouring of a graph G is an assignment of colours to the vertices of G such that two vertices of the same colour have identical sets of colours in their neighbourhoods. We show that the problem of finding a role colouring with 1 < k < n colours is NP-hard for planar graphs. We show that restricting the problem to trees yields a polynomially solvable case, as long as k is either constant or has a constant difference with n, the number of vertices in the tree. Finally, we prove that cographs are always k-role-colourable for 1 < k <= n and construct such a colouring in polynomial time.