Everett, Martin G. and Borgatti, Stephen P. (1996) Exact colorations of graphs and digraphs. Social Networks, 18 (4). pp. 319-331. ISSN 0378-8733 (doi:10.1016/0378-8733(95)00286-3)

Full text not available from this repository.

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.

Item Type:	Article
Uncontrolled Keywords:	graphs, digraphs, coloration
Subjects:	Q Science > QA Mathematics
Pre-2014 Departments:	School of Computing & Mathematical Sciences
Related URLs:	Publisher
Last Modified:	14 Oct 2016 09:00
URI:	http://gala.gre.ac.uk/id/eprint/377

Actions (login required)

View Item