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

Abstract

An 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.