Exact colorations of graphs and digraphs

Martin G. Everett; Stephen P. Borgatti

doi:10.1016/0378-8733(95)00286-3

Exact colorations of graphs and digraphs

Martin G. Everett, Stephen P. Borgatti

Management

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

15 Scopus citations

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.

Original language	English
Pages (from-to)	319-331
Number of pages	13
Journal	Social Networks
Volume	18
Issue number	4
DOIs	https://doi.org/10.1016/0378-8733(95)00286-3
State	Published - Oct 1996

ASJC Scopus subject areas

Anthropology
Sociology and Political Science
General Social Sciences
General Psychology

Access to Document

10.1016/0378-8733(95)00286-3

Cite this

@article{af5dda79a95341b183dea000914c9c0b,

title = "Exact colorations of graphs and digraphs",

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.",

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

year = "1996",

month = oct,

doi = "10.1016/0378-8733(95)00286-3",

language = "English",

volume = "18",

pages = "319--331",

number = "4",

}

TY - JOUR

T1 - Exact colorations of graphs and digraphs

AU - Everett, Martin G.

AU - Borgatti, Stephen P.

PY - 1996/10

Y1 - 1996/10

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

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

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

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

U2 - 10.1016/0378-8733(95)00286-3

DO - 10.1016/0378-8733(95)00286-3

M3 - Article

AN - SCOPUS:0030269239

SN - 0378-8733

VL - 18

SP - 319

EP - 331

JO - Social Networks

JF - Social Networks

IS - 4

ER -

Exact colorations of graphs and digraphs

Abstract

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this