The classification conjecture for perfect colorings of infinite circulant graphs with odd distances
The classification conjecture for perfect colorings of infinite circulant graphs with odd distances
Let and be positive integers. Write for the set of the first positive odd integers, and let denote the infinite circulant graph whose vertices are the integers, with two vertices adjacent when their difference belongs to up to sign. A perfect -coloring is a coloring with 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 -colorings of consists of perfect colorings induced from perfect colorings of the infinite path graph and of the finite circulant graphs for .
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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.