Computing role assignments of split graphs

A k-role assignment of a simple graph G   is a surjective function r:V(G)→{1,…,k}r:V(G)→{1,…,k} where {r(u′):u′∈N(u)}={r(v′):v′∈N(v)}{r(u′):u′∈N(u)}={r(v′):v′∈N(v)} for every pair u,v∈V(G)u,v∈V(G) with r(u)=r(v)r(u)=r(v). This concept appears in the context of social networks. It is known that the problem of finding a 2-role assignment of chordal graphs can be solved in linear time and that deciding whether a graph of this class admits a k  -role assignment, for any fixed k≥3k≥3, is NP-complete. In this work, we investigate this problem on split graphs, a subclass of chordal graphs. We characterize the split graphs admitting a 3-role assignment. Such result leads to a linear time algorithm for this case. Furthermore, we prove that deciding whether a split graph has a k-role assignment is NP-complete for any fixed k≥4k≥4.