Аннотация:

A coloring of vertices of a given graph is called perfect if the color structure of each sphere of radius 1 in the graph depends only on the color of the sphere center. The crossed prism graph is a graph obtained by taking two disjoint infinite cycles (the vertices of the upper cycle are even integers, and the vertices of the lower cycle are odd ones) and adding edges $(i, i + 3)$ for $i = 4p$ and $(i, i - 1)$ for $i = 4p + 2$ ($p \in \mathbb{Z}$). A complete description of perfect colorings with an arbitrary number of colors is obtained for crossed prism graph. It is proved that all its perfect colorings are exhausted by disjunctive ones, except for six sporadic cases.