Izvestiya of Saratov University.

Mathematics. Mechanics. Informatics

ISSN 1816-9791 (Print)
ISSN 2541-9005 (Online)

For citation:

Razumovsky P. V., Abrosimov M. B. Generation of colored graphs with isomorphism rejection. Izvestiya of Saratov University. Mathematics. Mechanics. Informatics, 2021, vol. 21, iss. 2, pp. 267-277. DOI: 10.18500/1816-9791-2021-21-2-267-277, EDN: TRQZAM

This is an open access article distributed under the terms of Creative Commons Attribution 4.0 International License (CC-BY 4.0).
Published online: 
Full text:
(downloads: 1413)
Article type: 

Generation of colored graphs with isomorphism rejection

Razumovsky Peter Vladimirovich, Saratov State University
Abrosimov Mikhail Borisovich, Saratov State University

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.

This work was supported by the Ministry of Science and Higher Education of the Russian Federation in the framework of the state task (project No. FSRR-2020-0006).
  1. McKay B. D., Piperno A. Practical graph isomorphism, II. Journal of Symbolic Computation, 2013, vol. 60, pp. 94–112. https://doi.org/10.1016/j.jsc.2013.09.003
  2. McKay B. D., Piperno A. Nauty and Traces: Graph canonical labeling and automorphism group computation. Available at: https://pallini.di.uniroma1.it/ (accessed 1 May 2020).
  3. Meringer M. Fast generation of regular graphs and construction of cages. Journal of Graph Theory, 1999, vol. 30, pp. 137–146. https://doi.org/10.1002/(SICI)1097- 0118(199902)30:2<_x0031_37:_x003a_AID-JGT7>3.0.CO;2-G
  4. Brinkmann G., Goedgebeur J., McKay B. D. Generation of cubic graphs. Discrete Mathematics and Theoretical Computer Science. DMTCS, 2011, vol. 13, no. 2, pp. 69–79.
  5. Brinkmann G. Isomorphism rejection in structure generation programs. In: P. Hansen, P. W. Fowler, M. Zheng, eds. Discrete Mathematical Chemistry. DIMACS Series in Discrete Mathematics and Theoretical Computer Science, 2000, vol. 51, pp. 25–38.
  6. Hayes J. P. A graph model for fault-tolerant computing system. IEEE Transactions on Computers, 1976, vol. C-25, no. 9, pp. 875–884. https://doi.org/10.1109/TC.1976.1674712
  7. Jensen T., Toft B. Graph Coloring Problems. Wiley-Interscience, 1994. 320 p.
  8. L. W. Beineke, R. J. Wilson, eds. Topics in Chromatic Graph Theory. Cambridge, Cambridge University Press, 2015. 370 p. (Encyclopedia of Mathematics and its Applications 156). https://doi.org/10.1017/CBO9781139519793
  9. Lewis R. M. R. A Guide to Graph Colouring. Algorithms and Applications. Springer, Cham, 2016. 253 p.
  10. Bogomolov A. M., Salii V. N. Algebraicheskie osnovy teorii diskretnykh sistem [Algebraic Foundations of the Theory of Discrete Systems]. Moscow, Nauka, 1997. 368 p (in Russian).
  11. Harary F. Graph Theory. Addison-Wesley, 1969. 275 p. (Russ. ed.: Moscow, Mir, 1973. 296 p.).
  12. Abrosimov M. B., Razumovsky P. V. About generation of non-isomorphic vertex k-colorings. Prikladnaya Diskretnaya Matematika. Supplement, 2017, no. 10, pp. 136–138 (in Russian). https://doi.org/10.17223/2226308X/10/53
  13. Razumovsky P. V., Abrosimov M. B. About generation of non-isomorphic k-colorings by McKay’s method. In: Komp’iuternye nauki i informastionnye tekhnologii [Computer Science and Information Technologies: Proceedings of the International Scientific Conference]. Saratov, Publishing Center “Nauka”, 2018, pp. 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, pp. 173–176 (in Russian). https://doi.org/10.17223/2226308X/12/48