Role coloring bipartite graphs (Q2081494)

The \(k\)-role colouring problem has as input an undirected graph \(G\) and a positive integer \(k\). The question is then whether there is a surjective function \(\alpha: V(G)\) to \(\{1,2,\ldots k\{\) such that if \(\alpha(u)=\alpha(v)\) then, letting \(N(w)\) denote the neighbourhood of a vertex \(w\) as usual, we have \(\alpha(N(u))=\alpha(N(v))\). This notion apparently has applications in social science. Previous work by various groups of authors had shown that for general graphs this problem is polynomial-time soluble when \(k=1\) and is NP-complete for \(k\geq 2\). The aim of the paper under review is to study what happens for the class of bipartite graphs. The \(k\)-role colouring problem is trivial for \(k\leq 2\) for this class. The main contribution of the paper is to show that the \(k\)-role colouring problem is NP-complete on bipartite graphs for fixed \(k\geq 3\). The paper also gives a characterisation of so-called bipartite chain graphs which are 3-role-colourable and shows that 2-role colouring is NP complete on the class of ``almost bipartite graphs''.