Izvestiya of Saratov University. Mathematics. Mechanics. Informatics
General information
Latest issue
Impact factor

Search papers
Search references

Latest issue
Current issues
Archive issues
What is RSS

Izv. Saratov Univ. Math. Mech. Inform.:

Personal entry:
Save password
Forgotten password?

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

This article is cited in 1 scientific paper (total in 1 paper)

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
Received: 20.06.2020
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
\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

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

    SHARE: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru

    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  mathnet  crossref
  • Известия Саратовского университета. Новая серия. Серия Математика. Механика. Информатика
    Number of views:
    This page:18
    Full text:9

    Contact us:
     Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2021