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 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