EXACT COLORATIONS OF GRAPHS AND DIGRAPHS

A coloration is an exact regular coloration if whenever two vertices a re colored the same they have identically colored neighborhoods. For e xample, if one of the two vertices that are colored the same is connec ted 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 m athematical 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 colo rations, and discuss how the CATREGE algorithm can be extended to find the maximal exact regular coloration of a graph.