Geodesic
Generation of colored graphs with isomorphism rejection
Izvestiya of Saratov University. Mathematics. Mechanics. Informatics, Tome 21 (2021) no. 2, pp. 267-277 
P. V. Razumovskii; M. B. Abrosimov. Generation of colored graphs with isomorphism rejection. Izvestiya of Saratov University. Mathematics. Mechanics. Informatics, Tome 21 (2021) no. 2, pp. 267-277. http://geodesic.mathdoc.fr/item/ISU_2021_21_2_a12/
@article{ISU_2021_21_2_a12,
     author = {P. V. Razumovskii and M. B. Abrosimov},
     title = {Generation of colored graphs with isomorphism rejection},
     journal = {Izvestiya of Saratov University. Mathematics. Mechanics. Informatics},
     pages = {267--277},
     year = {2021},
     volume = {21},
     number = {2},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/ISU_2021_21_2_a12/}
}
TY  - JOUR
AU  - P. V. Razumovskii
AU  - M. B. Abrosimov
TI  - Generation of colored graphs with isomorphism rejection
JO  - Izvestiya of Saratov University. Mathematics. Mechanics. Informatics
PY  - 2021
SP  - 267
EP  - 277
VL  - 21
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/ISU_2021_21_2_a12/
LA  - ru
ID  - ISU_2021_21_2_a12
ER  - 
%0 Journal Article
%A P. V. Razumovskii
%A M. B. Abrosimov
%T Generation of colored graphs with isomorphism rejection
%J Izvestiya of Saratov University. Mathematics. Mechanics. Informatics
%D 2021
%P 267-277
%V 21
%N 2
%U http://geodesic.mathdoc.fr/item/ISU_2021_21_2_a12/
%G ru
%F ISU_2021_21_2_a12

Voir la notice de l'article provenant de la source Math-Net.Ru

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.

[1] McKay B. D., Piperno A., “Practical graph isomorphism, II”, Journal of Symbolic Computation, 60 (2013), 94–112 | DOI | MR

[2] McKay B. D., Piperno A., Nauty and Traces: Graph canonical labeling and automorphism group computation, (accessed 1 May 2020) https://pallini.di.uniroma1.it/

[3] Meringer M., “Fast generation of regular graphs and construction of cages”, Journal of Graph Theory, 30 (1999), 137–146 | 3.0.CO;2-G class='badge bg-secondary rounded-pill ref-badge extid-badge'>DOI | MR | Zbl

[4] Brinkmann G., Goedgebeur J., McKay B. D., “Generation of cubic graphs”, Discrete Mathematics and Theoretical Computer Science, DMTCS, 13:2 (2011), 69–79 | MR

[5] Brinkmann G., “Isomorphism rejection in structure generation programs”, Discrete Mathematical Chemistry, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, 51, eds. P. Hansen, P. W. Fowler, M. Zheng, 2000, 25–38 | DOI | MR | Zbl

[6] Hayes J. P., “A graph model for fault-tolerant computing system”, IEEE Transactions on Computers, C-25:9 (1976), 875–884 | DOI | MR

[7] Jensen T., Toft B., Graph Coloring Problems, Wiley-Interscience, 1994, 320 pp. | MR

[8] L. W. Beineke, R. J. Wilson (eds.), Topics in Chromatic Graph Theory, Encyclopedia of Mathematics and its Applications, 156, Cambridge University Press, Cambridge, 2015, 370 pp. | DOI | MR | Zbl

[9] Lewis R. M. R., A Guide to Graph Colouring. Algorithms and Applications, Springer, Cham, 2016, 253 pp. | DOI | MR | Zbl

[10] Bogomolov A. M., Salii V. N., Algebraic Foundations of the Theory of Discrete Systems, Nauka, M., 1997, 368 pp. (in Russian) | MR

[11] Harary F., Graph Theory, Addison-Wesley, 1969, 275 pp. | MR | Zbl

[12] Abrosimov M. B., Razumovsky P. V., “About generation of non-isomorphic vertex $k$-colorings”, Prikladnaya Diskretnaya Matematika. Supplement, 2017, no. 10, 136–138 (in Russian) | DOI

[13] Razumovsky P. V., Abrosimov M. B., “About generation of non-isomorphic $k$-colorings by McKay's method”, Computer Science and Information Technologies, Proceedings of the International Scientific Conference, Publishing Center “Nauka”, Saratov, 2018, 318–320 (in Russian)

[14] Abrosimov M. B., Razumovsky P. V., “About non-isomorphic graph colouring generating by Read – Faradzhev method”, Applied Discrete Mathematics. Supplement, 2019, no. 12, 173–176 (in Russian) | DOI