About generation of non-isomorphic vertex k-colorings
In this paper, we study the generation problem for non-isomorphic vertex and edge k-colorings of a given graph. An algorithm for generating all the non-isomorphic vertex k-colorings of a graph by the Reed - Faradzhev method without using an isomorphism testing technique is suggested. The problem of generating edge k-colorings is reduced to the problem of generating vertex k-colorings.
Download file
Counter downloads: 189
Keywords
граф, раскраска, изоморфизм, вершинная раскраска, рёберная раскраска, graph, isomorphism, coloring, vertex coloringAuthors
| Name | Organization | |
| Abrosimov M. B. | Chernyshevsky Saratov State University | mic@rambler.ru |
| Razumovsky P. V. | Chernyshevsky Saratov State University | shprotby@gmail.com |
References
Абросимов М. Б. Графовые модели отказоустойчивости. Саратов: Изд-во Сарат. ун-та, 2012. 192 с.
Харари Ф. Теория графов. М.: Мир, 1973. 296с.
http://users.cecs.anu.edu.au/bdm/nauty/ - Nauty and Traces: Graph Canonical Labeling and Automorphism Group Computation. 2016.
McKay B. D. and Piperno A. Practical graph isomorphism // J. Symbolic Computation. 2013. V.2. No. 60. P. 94-112.
