On the complexity of role colouring planar graphs, trees and cographs

We prove several results about the complexity of the role colouring problem. A role colouringof 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. Published by Elsevier B.V.