Izv. Saratov Univ. Math. Mech. Inform., 2021, Volume 21, Issue 2, Pages 267–277
This article is cited in 1 scientific paper (total in 1 paper)
Generation of colored graphs with isomorphism rejection
P. V. Razumovskii, M. B. Abrosimov
Saratov State University, 83 Astrakhanskaya St., Saratov 410012, Russia
In the article we consider graphs whose vertices or edges are colored in a given number of colors — vertex and edge colorings. The study of colorings of graphs began in the middle of the 19th century, but the main attention is paid to proper colorings, in which the restriction applies that the colors of adjacent vertices or edges must be different. This paper considers colorings of graphs without any restrictions. We study the problem of generating all non-isomorphic vertex and edge $k$-colorings of a given graph without direct checking for isomorphism. The problem of generating non-isomorphic edge $k$-colorings is reduced to the problem of constructing all vertex $k$-colorings of a graph. Methods for generating graphs without direct checking for isomorphism or isomorphism rejection are based on the method of canonical representatives. The idea of the method is that a method for encoding graphs is proposed and a certain rule is chosen according to which one of all isomorphic graphs is declared canonical. All codes are built and only the canonical ones are accepted. Often, the representative with the largest or smallest code is chosen as the canonical one. In practice, generating all codes requires large computational resources; therefore, various methods of enumeration optimization are used. The paper proposes two algorithms for solving the problem of generating vertex $k$-colorings with isomorphism rejection by McKay and Reed – Faradzhev methods. A comparison of the proposed algorithms for generating colorings on two classes of graphs — paths and cycles is made. Computational experiments show that the Reed – Faradzhev method is faster for paths and cycles.
graph, graph labeling, graph coloring, color graph, generator.
PDF file (177 kB)
P. V. Razumovskii, M. B. Abrosimov, “Generation of colored graphs with isomorphism rejection”, Izv. Saratov Univ. Math. Mech. Inform., 21:2 (2021), 267–277
Citation in format AMSBIB
\by P.~V.~Razumovskii, M.~B.~Abrosimov
\paper Generation of colored graphs with isomorphism rejection
\jour Izv. Saratov Univ. Math. Mech. Inform.
Citing articles on Google Scholar:
Related articles on Google Scholar:
This publication is cited in the following articles:
P. V. Razumovskii, M. B. Abrosimov, “Skhemy postroeniya minimalnykh vershinnykh $1$-rasshirenii polnykh dvukhtsvetnykh grafov”, PDM. Prilozhenie, 2021, no. 14, 165–168
|Number of views:|