Role coloring of various families of snark graphs

Source abstract

Social networks are an integral part of everyday life. A social network can be envisioned as a graph, where the vertices represent individuals and the edges indicate relationships between them, enabling the study of their behavior. This gives rise to the decision problem known as $k$-role coloring. A $k$-role coloring of a graph $G$ is an assignment of exactly $k$ colors to its vertices such that any two vertices receiving the same color have identical sets of colors in their neighborhoods. A $k$-role coloring is trivial when $k = 1$ or $k = n$, and the problem is NP-complete on general graphs for all $k \geq 2$. In this paper, we study the class of snark graphs. A snark is a special class of $3$-regular graphs, and we determine the $k$-role colorings of snarks for $k \leq 3$. Received: 20 January 2025 | Revised: 10 June 2026 | Accepted: 19 August 2026