Role colouring a graph (Q1177106)

A role colouring of a graph is an assignment of a colour to each vertex such that whenever vertices \(x\) and \(y\) have the same colour then the colour sets used on the neighbours of \(x\) and of \(y\) respectively are also the same. (Note that a role colouring is not a usual proper colouring of the graph: vertices joined by an edge may have the same colour in a role colouring.) The vertices of a colour class in a role colouring are thought of as individuals with the same social role. Role colourings have been studied earlier by White and Reitz [Social Networks 5, 193-235 (1983)] using the term ``regular equivalence'' for individuals with the same social role. In the present note the authors study the lattice that the role-colour partitions of a graph \(G\) form with the elements ordered by the refinement relation. Moreover they exhibit an example of a graph (on 10 vertices) having only the two trivial role colourings (all vertices coloured the same or all vertices coloured differently). It is proved that for any such graph on \(\geq 3\) vertices the automorphism group consists of the identity.