The classification conjecture for perfect colorings of infinite circulant graphs with odd distances

Let kk and nn be positive integers. Write DnD_n for the set of the first nn positive odd integers, and let Ci(Dn)\mathrm{Ci}_\infty(D_n) denote the infinite circulant graph whose vertices are the integers, with two vertices adjacent when their difference belongs to DnD_n up to sign. A perfect kk-coloring is a coloring with kk colors for which the number of neighbors of each color is determined solely by the color of the vertex.

Classification conjecture. The set of perfect kk-colorings of Ci(Dn)\mathrm{Ci}_\infty(D_n) consists of perfect colorings induced from perfect colorings of the infinite path graph and of the finite circulant graphs Cit(Dn)\mathrm{Ci}_t(D_n) for t=4n2,4n,4n+2t=4n-2,4n,4n+2.

The conjecture proposes that all perfect colorings in this family arise from the previously classified perfect colorings of the infinite path or from these three finite circulant graphs. The surrounding results establish periodicity of perfect colorings, but the stated classification is not resolved here.

Sources & referencesView supporting material

Primary source

O. G. Parshina and M. A. Lisitsyna, “The perfect 2-colorings of infinite circulant graphs with a continuous set of odd distances”, arXiv:1903.09444 (2020).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.