2014/08/14 by Purcell, Christopher, Rombach, M. Puck · 1 citation
#68R10 #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #F.2.2 #FOS: Computer and information sciences #G.2.2
paper · doi:10.48550/arxiv.1408.5412
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