  A k-role coloring alpha of a graph G is an assignment of k colors to the
vertices of G such that if any two vertices are assigned the same color, then
their neighborhood are assigned the same set of colors. That is, if alpha(u) =
alpha(v) for a pair of vertices u and v, then the set of colors assigned to
N(u) and N(v) are the same (where N(u) is the set of neighbors of u). By
definition, every graph on n vertices admits an n-role coloring. While for
every graph on n vertices, it is trivial to decide if it admits a 1-role
coloring, determining whether a graph admits a k-role coloring is a notoriously
hard problem for k greater than 1. In fact, it is known that k-Role coloring is
NP-complete for k greater than 1 on arbitrary graphs. There has been extensive
research on the complexity of k-role coloring on various hereditary graph
classes. Furthering this direction of research, we show that k-Role coloring is
NP-complete on bipartite graphs for k greater than 2 (while it is trivial for k
= 2). We complement the hardness result by characterizing 3-role colorable
bipartite chain graphs, leading to a polynomial-time algorithm for 3-Role
coloring for this class of graphs. We further show that 2-Role coloring is
NP-complete for graphs that are d vertices or edges away from the class of
bipartite graphs, even when d = 1.
