Skip to main content
Article
Exact colorations of graphs and digraphs
Social Networks (1996)
  • Martin G. Everett
  • Stephen P. Borgatti
Abstract
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.
Publication Date
October, 1996
Citation Information
Martin G. Everett and Stephen P. Borgatti. "Exact colorations of graphs and digraphs" Social Networks Vol. 18 Iss. 4 (1996)
Available at: http://works.bepress.com/steveborgatti/18/