About 4-Role Assignment for Strong Product Graphs

An 𝑟-role assignment in a graph 𝐺 consists of labeling the vertices with 𝑟 distinct roles such that vertices with the same role have the same set of roles in their adjacent vertices. The role assignment problem has applications in social, biological, and technological networks. It is known that determining whether a graph admits an 𝑟-role assignment is NP-complete for 𝑟 ≥ 2. In this paper, we investigate the problem of 4-role assignment in the strong product of graphs 𝐺 ⊠ 𝐻. We prove that the problem is NP-complete when 𝐺 and 𝐻 are nontrivial graphs. On the other hand, we show that when 𝐺 and 𝐻 are bipartite graphs, cographs, or split graphs, their strong product always admits a 4-role assignment, making the problem solvable in constant time, or linear time in the case of chordal graphs.