Computing a 3-role assignment is polynomial-time solvable on complementary prisms
<|reference_start|>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 vertices are the distinct $r$ roles, and there is an edge between two roles whenever there are two related 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. We 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.<|reference_end|>
@article{castonguay2024computing,
    title={Computing a 3-role assignment is polynomial-time solvable on
  complementary prisms},
    author={Diane Castonguay, Elis^angela S. Dias, Fernanda N. Mesquita, Julliano
  R. Nascimento},
    journal={arXiv preprint arXiv:2402.06068},
    year={2024},
    archivePrefix={arXiv},
    eprint={2402.06068},
    primaryClass={cs.DM math.CO}
}