2026-02-262026-02-262026CASTONGUAY, Diane et al. Computing a 3-Role assignment is polynomial-time solvable on complementary prisms. International Journal of Foundations of Computer Science, Singapura, v. 37, n. 2, p. 325-348, 2026. DOI: 10.1142/S012905412550011X. Disponível em: https://www.worldscientific.com/doi/10.1142/S012905412550011X?srsltid=AfmBOoqrNOSU7sam1H_EI6NNOEvqE6oQKiS3TrNb6Q7BPHFHsMORZEAo. Acesso em: 12 fev. 2026.0129-0541e- 1793-6373https://www.worldscientific.com/doi/10.1142/S012905412550011X?srsltid=AfmBOoqrNOSU7sam1H_EI6NNOEvqE6oQKiS3TrNb6Q7BPHFHsMORZEAoAn 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 vertices are the distinct r roles, and there is an edge between two roles whenever there are two adjacent vertices in the graph G that correspond to these roles. We consider complementary prisms, which are graphs formed from the disjoint union of the graph with its respective complement, adding the edges of a perfect matching between their corresponding vertices. In this work, we characterize the complementary prisms that do not admit a 3-role assignment and highlight that all of them are complementary prisms of disconnected bipartite graphs. Moreover, using our findings, we show that the problem of deciding whether a complementary prism has a 3-role assignment can be solved in polynomial time.engAcesso RestritoRole assignmentComplementary prismPolynomial timeArtigo10.1142/S012905412550011X