On perfect colorings of in nite multipath graphs

Abstract

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. Let n be a positive integer. We consider a lexicographic product of the infinite path graph and a graph G that can be either the complete or empty graph on n vertices. We give a complete description of perfect colorings with an arbitrary number of colors of such graph products.