Role colouring a graph

Martin G. Everett, Steve Borgatti

Research output: Contribution to journalArticlepeer-review

62 Scopus citations


The role colouring of a graph is an assignment of colours to the vertices which obeys the rule that two vertices are coloured the same only if their neighbourhoods have the same colour set. We investigate the set of role colourings for a graph proving that it forms a lattice. We also show that this lattice can be trivial and this can only occur if the graph has a trivial automorphism group.

Original languageEnglish
Pages (from-to)183-188
Number of pages6
JournalMathematical Social Sciences
Issue number2
StatePublished - Apr 1991


  • Graph
  • automorphism group
  • lattice

ASJC Scopus subject areas

  • Sociology and Political Science
  • General Social Sciences
  • General Psychology
  • Statistics, Probability and Uncertainty


Dive into the research topics of 'Role colouring a graph'. Together they form a unique fingerprint.

Cite this