RUS  ENG
Full version
JOURNALS // Sibirskie Èlektronnye Matematicheskie Izvestiya [Siberian Electronic Mathematical Reports] // Archive

Sib. Èlektron. Mat. Izv., 2024 Volume 21, Issue 1, Pages 188–195 (Mi semr1676)

Discrete mathematics and mathematical cybernetics

The perfect colorings of circulant graphs with a large number of colors

M. A. Lisitsynaa, S. V. Avgustinovichb

a Mozhaisky Military Space Academy, Zhdanovskaya, 13, 197198, St Petersburg, Russia
b Sobolev Institute of Mathematics, pr. Koptyuga, 4, 630090, Novosibirsk, Russia

Abstract: An infinite circulant graph with a continuous set of distances is a graph, whose set of vertices is the set of integers, and two vertices $i$ and $j$ are adjacent if $|i-j| \in \{1,2,…,n\}$. We study perfect colorings of such graph with $k$ colors for $k$ at least $3n+3$. A complete description of them is obtained.

Keywords: perfect coloring, infinite circulant graph, $k$-motley fragment.

UDC: 519.174.7

MSC: 05C50

Received November 24, 2023, published February 28, 2024

DOI: doi.org/10.33048/semi.2024.21.013



© Steklov Math. Inst. of RAS, 2025