On the Complexity of Role Colouring Planar Graphs, Trees and Cographs

Christopher Purcell, M. Puck Rombach

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