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 2. In fact, k-role coloring is known to be NP-complete for k 2 on general graphs. In this paper, we determine k-role coloring of the rooted product of various graphs.
Download file
Counter downloads: 3
- Title Role coloring of graphs from rooted products
- Headline Role coloring of graphs from rooted products
- Publesher
Tomsk State University - Issue Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics 68
- Date:
- DOI 10.17223/20710410/68/6
Keywords
role coloring, role graph, rooted product, binary productAuthors
References
Bondy J. A. and Murty U. S. R. Graph Theory. London, Springer, 2008.
Everett M. G. and Borgatti S. Role colouring a graph. Math. Social Sci., 1991, vol. 21, no. 2, pp.183-188.
Pandey S. and Sahlot V. Role coloring bipartite graphs. Discrete Appl. Math., 2022, vol. 322, pp.276-285.
Fiala J. and Paulusma D. A complete complexity classification of the role assignment problem. Theor.Comput. Sci., 2005, vol. 349, no. 1, pp. 67-81.
Roberts F. S. and Sheng L. How hard is it to determine if a graph has a 2 role assignment? Networks, 2001, vol. 37, no. 2, pp. 67-73.
Van't Hof P., Paulusma D., and van Rooij J.M.Computing role assignments of chordal graphs. Theor.Comput. Sci., 2010, vol. 411, no. 40-42, pp. 3601-3613.
Heggernes P., van't Hof P., and Paulusma D.Computing role assignments of proper interval graphs in polynomial time. LNCS, 2011, vol. 6460, pp. 167-180.
Purcell C. and Rombach P. On the complexity of role colouring planar graphs, trees and cographs. J. Discrete Algorithms, 2015, vol. 35, pp. 1-8.
Purcell C. and Rombach P. Role colouring graphs in hereditary classes. Theor.Comput. Sci., 2021, vol. 876, pp. 12-24.
Dourado M. C.Computing role assignments of split graphs. Theor.Comput. Sci., 2016, vol. 635, pp. 74-84.
Castonguay D., Dias E. S., Mesquita F. N., and Nascimento J. R. Computing role assignments of cartesian product of graphs. RAIRO-Operations Research, 2023, vol. 57, no. 3, pp. 10751086.
Godsil C. D. and McKay B. D. A new graph product and its spectrum. Bull. Australian Math. Society, 1978, vol. 18, no. 1, pp. 21-28.
Role coloring of graphs from rooted products | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2025. № 68. DOI: 10.17223/20710410/68/6
Download full-text version
Counter downloads: 68