Role colouring a graph

Martin G. Everett; Steve Borgatti

doi:10.1016/0165-4896(91)90080-B

Role colouring a graph

Martin G. Everett, Steve Borgatti

Management

Research output: Contribution to journal › Article › peer-review

62 Scopus citations

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.

Original language	English
Pages (from-to)	183-188
Number of pages	6
Journal	Mathematical Social Sciences
Volume	21
Issue number	2
DOIs	https://doi.org/10.1016/0165-4896(91)90080-B
State	Published - Apr 1991

Keywords

Graph
automorphism group
lattice

ASJC Scopus subject areas

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

Access to Document

10.1016/0165-4896(91)90080-B

Cite this

@article{db20b5aa18a0477da2a9e4997b10e6a7,

title = "Role colouring a graph",

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, automorphism group, lattice",

author = "Everett, {Martin G.} and Steve Borgatti",

year = "1991",

month = apr,

doi = "10.1016/0165-4896(91)90080-B",

language = "English",

volume = "21",

pages = "183--188",

number = "2",

}

TY - JOUR

T1 - Role colouring a graph

AU - Everett, Martin G.

AU - Borgatti, Steve

PY - 1991/4

Y1 - 1991/4

N2 - 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.

AB - 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.

KW - Graph

KW - automorphism group

KW - lattice

UR - http://www.scopus.com/inward/record.url?scp=0000938084&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0000938084&partnerID=8YFLogxK

U2 - 10.1016/0165-4896(91)90080-B

DO - 10.1016/0165-4896(91)90080-B

M3 - Article

AN - SCOPUS:0000938084

SN - 0165-4896

VL - 21

SP - 183

EP - 188

JO - Mathematical Social Sciences

JF - Mathematical Social Sciences

IS - 2

ER -

Role colouring a graph

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this