Role coloring of graphs from rooted products

A $k$-role coloring is an assignment of $k$ colors to the vertices of a graph such that if any two vertices receive the same color, then the set of colors assigned to their neighborhood will also be the same. Any graph with $n$ vertices can have $n$-role coloring. Although it is easy to determine whether a graph with $n$ vertices accepts a $1$-role coloring, the challenge of $k$-role coloring is known to be difficult for $k \ge 2$. In fact, $k$-role coloring is known to be NP-complete for $k\ge 2$ on general graphs. In this paper, we determine $k$-role coloring of the rooted product of various graphs.