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

详细

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.