Role coloring of various families of snark graphs
DOI:
https://doi.org/10.13069/jacodesmath.v14i1.363Keywords:
Role coloring, Role graph, Snark graph, Cubic graphAbstract
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
Downloads
References
D. Blanuša, Problem cetiriju boja, Glas. Mat.-Fiz. Astron. Ser. II 1 (1946) 31–42.
J. A. Bondy and U. S. R. Murty, Graph Theory, vol. 244 in Graduate Texts in Mathematics, Springer, London (2008).
D. Castonguay, E. S. Dias, F. N. Mesquita, and J. R. Nascimento, Computing role assignments of cartesian product of graphs, RAIRO - Oper. Res. 57(3) (2023) 1075–1086.
A. Cavicchioli, M. Meschiari, B. Ruini, and F. Spaggiari, A survey on snarks and new results: Products, reducibility and a computer search, J. Graph Theory 28(2) (1998) 57–86.
M. C. Dourado, Computing role assignments of split graphs, Theoret. Comput. Sci. 635 (2016) 74–84.
M. G. Everett and S. Borgatti, Role colouring a graph, Math. Social Sci. 21(2) (1991) 183–188.
L. Ferrarini, G. Mazzuoccolo, and V. Mkrtchyan, Normal 5-edge-colorings of a family of Loupekhine snarks, AKCE Int. J. Graphs Comb. 17(3) (2020) 720–724.
J. Fiala and D. Paulusma, A complete complexity classification of the role assignment problem, Theoret. Comput. Sci. 349(1) (2005) 67–81.
K. K. Galv\~ao, Developments of Fulkerson's conjecture, Master's thesis, Institute of Computing, University of Campinas, Campinas, Brazil (2013).
M. K. Goldberg, Construction of class 2 graphs with maximum vertex degree 3, J. Combin. Theory Ser. B 31(3) (1981) 282–291.
R. Isaacs, Infinite families of nontrivial trivalent graphs which are not Tait colorable, Amer. Math. Monthly 82(3) (1975) 221–239.
R. Isaacs, Loupekhine's snarks: A bifamily of non-Tait-colorable graphs, Tech. Rep. 263, Department of Mathematical Sciences, The Johns Hopkins University, Baltimore, MD (1976).
S. Pandey and V. Sahlot, Role coloring bipartite graphs, Discrete Appl. Math. 322 (2022) 276–285.
C. Purcell and P. Rombach, On the complexity of role colouring planar graphs, trees and cographs, J. Discrete Algorithms 35 (2015) 1–8.
C. Purcell and P. Rombach, Role colouring graphs in hereditary classes, Theoret. Comput. Sci. 876 (2021) 12–24.
F. S. Roberts and L. Sheng, How hard is it to determine if a graph has a 2-role assignment?, Networks 37(2) (2001) 67–73.
L. Sheng, 2-Role assignments on triangulated graphs, Theoret. Comput. Sci. 304(1-3) (2003) 201–214.
G. Szekeres, Polyhedral decompositions of cubic graphs, Bull. Austral. Math. Soc. 8(3) (1973) 367–387.
J. J. Watkins, On the construction of snarks, Ars Combin. 16 (1983) 111–124.
J. J. Watkins, Snarks, Ann. New York Acad. Sci. 576(1) (1989) 606–622.
J. J. Watkins and R. J. Wilson, A survey of snarks, in: Graph Theory, Combinatorics, and Applications, vol. 2, Wiley, New York (1991) 1129–1144.
