Role colouring a graph

DOI10.1016/0165-4896(91)90080-BzbMath0771.05037OpenAlexW2002425555MaRDI QIDQ1177106

Martin G. Everett, Steve Borgatti

Publication date: 26 June 1992

Published in: Mathematical Social Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0165-4896(91)90080-b

zbMATH Keywords

latticeautomorphism grouprole colouring

Mathematics Subject Classification ID

Social networks; opinion dynamics (91D30) Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Coloring of graphs and hypergraphs (05C15)

Related Items (32)

Edge homogeneous colorings ⋮ Structural similarity: spectral methods for relaxed blockmodeling ⋮ Computing role assignments of split graphs ⋮ Parameterizing role coloring on forests ⋮ Mike Fellows: Weaving the Web of Mathematics and Adventure ⋮ Cantor--Bernstein type theorem for locally constrained graph homomorphisms ⋮ Defining and measuring trophic role similarity in food webs using regular equivalence ⋮ Obtaining online ecological colourings by generalizing first-fit ⋮ How hard is it to determine if a graph has a 2-role assignment? ⋮ An algorithmic framework for locally constrained homomorphisms ⋮ On the complexity of role colouring planar graphs, trees and cographs ⋮ Regular equivalence: General theory ⋮ Comparing Universal Covers in Polynomial Time ⋮ 2-role assignments on triangulated graphs. ⋮ Locally constrained graph homomorphisms and equitable partitions ⋮ An algorithmic framework for locally constrained homomorphisms ⋮ Computing role assignments of proper interval graphs in polynomial time ⋮ Locally constrained graph homomorphisms -- structure, complexity, and applications ⋮ Technology driven organizational structure of the firm ⋮ Computing Role Assignments of Proper Interval Graphs in Polynomial Time ⋮ Complexity of stability ⋮ Complexity of Stability. ⋮ On the computational complexity of partial covers of theta graphs ⋮ The role assignment model nearly fits most social networks ⋮ Computing role assignments of chordal graphs ⋮ Graph coloring, minimum-diameter partitioning, and the analysis of confusion matrices ⋮ Comparing universal covers in polynomial time ⋮ Assignment games, chromatic number, and exchange theory ⋮ Role coloring bipartite graphs ⋮ Locally constrained homomorphisms on graphs of bounded treewidth and bounded degree ⋮ Homogeneous colourings of graphs ⋮ A complete complexity classification of the role assignment problem

This page was built for publication: Role colouring a graph