Izvestiya of Saratov University. Mathematics. Mechanics. Informatics
 RUS  ENG JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB
 General information Latest issue Archive Impact factor Search papers Search references RSS Latest issue Current issues Archive issues What is RSS

 Izv. Saratov Univ. Math. Mech. Inform.: Year: Volume: Issue: Page: Find

 Izv. Saratov Univ. Math. Mech. Inform., 2021, Volume 21, Issue 2, Pages 267–277 (Mi isu892)

Scientific Part
Computer Sciences

Generation of colored graphs with isomorphism rejection

P. V. Razumovskii, M. B. Abrosimov

Saratov State University, 83 Astrakhanskaya St., Saratov 410012, Russia

Abstract: 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.

Key words: graph, graph labeling, graph coloring, color graph, generator.

 Funding Agency Grant Number Ministry of Education and Science of the Russian Federation FSRR-2020-0006 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).

DOI: https://doi.org/10.18500/1816-9791-2021-21-2-267-277

Full text: PDF file (177 kB)
References: PDF file   HTML file

Bibliographic databases:

UDC: 519.17
Revised: 12.10.2020

Citation: 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
\Bibitem{RazAbr21} \by P.~V.~Razumovskii, M.~B.~Abrosimov \paper Generation of colored graphs with isomorphism rejection \jour Izv. Saratov Univ. Math. Mech. Inform. \yr 2021 \vol 21 \issue 2 \pages 267--277 \mathnet{http://mi.mathnet.ru/isu892} \crossref{https://doi.org/10.18500/1816-9791-2021-21-2-267-277} \elib{https://elibrary.ru/item.asp?id=45797880} 

• http://mi.mathnet.ru/eng/isu892
• http://mi.mathnet.ru/eng/isu/v21/i2/p267

 SHARE:

Citing articles on Google Scholar: Russian citations, English citations
Related articles on Google Scholar: Russian articles, English articles

This publication is cited in the following articles:
1. P. V. Razumovskii, M. B. Abrosimov, “Skhemy postroeniya minimalnykh vershinnykh $1$-rasshirenii polnykh dvukhtsvetnykh grafov”, PDM. Prilozhenie, 2021, no. 14, 165–168