ГлавнаяАрхивRole coloring of graphs from rooted products

Role coloring of graphs from rooted products | Прикладная дискретная математика. 2025. № 68. DOI: 10.17223/20710410/68/6

k-Ролевая раскраска - это назначение k цветов вершинам графа таким образом, что если любые две вершины окрашены в один и тот же цвет, то набор цветов, назначенных их соседям, также будет одинаковым. Любой граф с n вершинами может бытв раскрашен n ролями. Легко определит, допускает ли граф с n вершинами 1-ролевую раскраску, но задача k-ролевой раскраски для k 2 на про-изволвных графах является NP-полной. В работе описана k-ролевая раскраска корневого произведения различных графов.
  • Title Role coloring of graphs from rooted products
  • Headline Role coloring of graphs from rooted products
  • Publesher Tomask State UniversityTomsk State University
  • Issue Прикладная дискретная математика 68
  • Date:
  • DOI 10.17223/20710410/68/6
Ключевые слова
ролевая раскаска, ролевой граф, корневое произведение, бинарное произведение
Авторы
Ссылки
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 | Прикладная дискретная математика. 2025. № 68. DOI: 10.17223/20710410/68/6
Role coloring of graphs from rooted products | Прикладная дискретная математика. 2025. № 68. DOI: 10.17223/20710410/68/6