Article ID Journal Published Year Pages File Type
431575 Journal of Discrete Algorithms 2015 8 Pages PDF
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

Keywords
Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Preview
On the complexity of role colouring planar graphs, trees and cographs
Authors
, ,