Role Coloring Bipartite Graphs

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.