Exact colorations of graphs and digraphs

Martin G. Everett, Stephen P. Borgatti

Research output: Contribution to journalArticlepeer-review

13 Scopus citations


A coloration is an exact regular coloration if whenever two vertices are colored the same they have identically colored neighborhoods. For example, if one of the two vertices that are colored the same is connected to three yellow vertices, two white and red, then the other vertex is as well. Exact regular colorations have been discussed informally in the social network literature. However they have been part of the mathematical literature for some time, though in a different format. We explore this concept in terms of social networks and illustrate some important results taken from the mathematical literature. In addition we show how the concept can be extended to ecological and perfect colorations, and discuss how the CATREGE algorithm can be extended to find the maximal exact regular coloration of a graph.

Original languageEnglish
Pages (from-to)319-331
Number of pages13
JournalSocial Networks
Issue number4
StatePublished - Oct 1996

ASJC Scopus subject areas

  • Anthropology
  • Sociology and Political Science
  • General Social Sciences
  • General Psychology


Dive into the research topics of 'Exact colorations of graphs and digraphs'. Together they form a unique fingerprint.

Cite this