Role colouring a graph
A role colouring of a graph is an assignment of a colour to each vertex such that whenever vertices \(x\) and \(y\) have the same colour then the colour sets used on the neighbours of \(x\) and of \(y\) respectively are also the same. (Note that a role colouring is not a usual proper colouring of the graph: vertices joined by an edge may have the same colour in a role colouring.) The vertices of a colour class in a role colouring are thought of as individuals with the same social role. Role colourings have been studied earlier by White and Reitz [Social Networks 5, 193-235 (1983)] using the term ``regular equivalence for individuals with the same social role. In the present note the authors study the lattice that the role-colour partitions of a graph \(G\) form with the elements ordered by the refinement relation. Moreover they exhibit an example of a graph (on 10 vertices) having only the two trivial role colourings (all vertices coloured the same or all vertices coloured differently). It is proved that for any such graph on \(\geq 3\) vertices the automorphism group consists of the identity.
- 2-role assignments on triangulated graphs.
- Obtaining online ecological colourings by generalizing first-fit
- Graph coloring, minimum-diameter partitioning, and the analysis of confusion matrices
- Role coloring bipartite graphs
- Defining and measuring trophic role similarity in food webs using regular equivalence
- Complexity of stability
- Locally constrained homomorphisms on graphs of bounded treewidth and bounded degree
- Locally constrained graph homomorphisms and equitable partitions
- On the computational complexity of partial covers of theta graphs
- How hard is it to determine if a graph has a 2-role assignment?
- Structural similarity: spectral methods for relaxed blockmodeling
- Computing role assignments of split graphs
- Mike Fellows: Weaving the Web of Mathematics and Adventure
- Computing role assignments of proper interval graphs in polynomial time
- Comparing Universal Covers in Polynomial Time
- scientific article; zbMATH DE number 1008448 (Why is no real title available?)
- Computing role assignments of proper interval graphs in polynomial time
- Locally constrained graph homomorphisms -- structure, complexity, and applications
- Assignment games, chromatic number, and exchange theory
- Regular equivalence: General theory
- Edge homogeneous colorings
- Homogeneous colourings of graphs
- The role assignment model nearly fits most social networks
- An algorithmic framework for locally constrained homomorphisms
- Complexity of Stability.
- An algorithmic framework for locally constrained homomorphisms
- Technology driven organizational structure of the firm
- Computing a 3-role assignment is polynomial-time solvable on complementary prisms
- Tabular intermediate logics comparison
- Computing role assignments of chordal graphs
- A complete complexity classification of the role assignment problem
- Parameterizing role coloring on forests
- Cantor--Bernstein type theorem for locally constrained graph homomorphisms
- On the complexity of role colouring planar graphs, trees and cographs
- Comparing universal covers in polynomial time
This page was built for publication: Role colouring a graph
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1177106)
