How hard is it to determine if a graph has a 2-role assignment?

Role assignments, introduced by Everett and Borgatti [2], who called them r ole colorings, formalize the idea, arising in the theory of social networks , that individuals of the same social role will relate in the same way to t he individuals playing counterpart roles. If G is a graph, a k-role assignm ent is a function r mapping the vertex set onto the set of integers {1,2,.. ., k} so that if r(x) = r(y) then the sets of roles assigned to the neighbo rs of x and y are the same. We ask how hard it is to determine if a graph h as a 2-role assignment and show that recognizing if a graph has a 2-role as signment is NP-complete. (C) 2001 John Wiley & Sons, Inc.