Skip to main content
Article
Role colouring a graph
Mathematical Social Sciences (1991)
  • Martin G. Everett
  • Steve Borgatti, University of South Carolina - Columbia
Abstract
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.
Keywords
  • Graph,
  • lattice,
  • automorphism group
Publication Date
April, 1991
Citation Information
Martin G. Everett and Steve Borgatti. "Role colouring a graph" Mathematical Social Sciences Vol. 21 Iss. 2 (1991)
Available at: http://works.bepress.com/steveborgatti/46/