Perfect colorings of the infinite circulant graph with distances 1 and 2
- Authors: Lisitsyna M.A.1, Parshina O.G.2,3
-
Affiliations:
- Marshal Budyonny Military Academy of Telecommunications
- Sobolev Institute of Mathematics
- Institut Camille Jordan
- Issue: Vol 11, No 3 (2017)
- Pages: 381-388
- Section: Article
- URL: https://journals.rcsi.science/1990-4789/article/view/212792
- DOI: https://doi.org/10.1134/S1990478917030097
- ID: 212792
Cite item
Abstract
A coloring of the vertex set in a graph is called perfect if all its identically colored vertices have identical multisets of colors of their neighbors. Refer as the infinite circulant graph with continuous set of n distances to the Cayley graph of the group ℤ with generator set {1, 2,..., n}. We obtain a description of all perfect colorings with an arbitrary number of colors of this graph with distances 1 and 2. In 2015, there was made a conjecture characterizing perfect colorings for the infinite circulant graphs with a continuous set of n distances. The obtained result confirms the conjecture for n = 2. The problem is still open in the case of n > 2.
Keywords
About the authors
M. A. Lisitsyna
Marshal Budyonny Military Academy of Telecommunications
Author for correspondence.
Email: lisicinama@ngs.ru
Russian Federation, Tikhoretskii pr. 3, St. Petersburg, 194064
O. G. Parshina
Sobolev Institute of Mathematics; Institut Camille Jordan
Email: lisicinama@ngs.ru
Russian Federation, pr. Akad. Koptyuga 4, Novosibirsk, 630090; 43 Boulevard du 11 novembre 1918, Villeurbanne Cedex, F-69622