Role coloring of graphs from rooted products

$k$-Ролевая раскраска — это назначение $k$ цветов вершинам графа таким образом, что если любые две вершины окрашены в один и тот же цвет, то набор цветов, назначенных их соседям, также будет одинаковым. Любой граф с $n$ вершинами может быть раскрашен $n$ ролями. Легко определить, допускает ли граф с $n$ вершинами $1$-ролевую раскраску, но задача $k$-ролевой раскраски для $k\ge 2$ на произвольных графах является NP-полной. В работе описана $k$-ролевая раскраска корневого произведения различных графов.