RUS  ENG
Full version
JOURNALS // Diskretnyi Analiz i Issledovanie Operatsii // Archive

Diskretn. Anal. Issled. Oper., 2017 Volume 24, Issue 3, Pages 20–34 (Mi da873)

This article is cited in 6 papers

Perfect colorings of the infinite circulant graph with distances 1 and 2

M. A. Lisitsynaa, O. G. Parshinabc

a Marshal Budyonny Military Academy of Telecommunications, 3 Tikhoretsky Ave., 194064 St. Petersburg, Russia
b Sobolev Institute of Mathematics, 4 Acad. Koptyug Ave., 630090 Novosibirsk, Russia
c Institut Camille Jordan, Université Claude Bernard Lyon 1, 43 Boulevard du 11 Novembre 1918, F-69622 Villeurbanne Cedex, France

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 $\mathbb{Z}$ with generator set $\{1,2,\ldots,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$. Bibliogr. 12.

Keywords: perfect coloring, circulant graph, equitable partition.

UDC: 519.174.7

Received: 02.12.2016
Revised: 30.03.2017

DOI: 10.17377/daio.2017.24.559


 English version:
Journal of Applied and Industrial Mathematics, 2017, 11:3, 381–388

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2024