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

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 are adjacent if they are on the distance 1, 2, ... or n. We study perfect colorings of such graph with k colors for k at least 3n+3. A complete description of them is obtained.