Computing a 3-role assignment is polynomial-time solvable on complementary prisms

Diane Castonguay, Elisângela S. Dias, Fernanda N. Mesquita +1

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 assi…