Computing a 3-role assignment is polynomial-time solvable on
complementary prisms
Computing a 3-role assignment is polynomial-time solvable on
complementary prisms
A $r$-role assignment of a simple graph $G$ is an assignment of $r$ distinct roles to the vertices of $G$, such that two vertices with the same role have the same set of roles assigned to related vertices. Furthermore, a specific $r$-role assignment defines a role graph, in which the …