О совершенных раскрасках бесконечных кратных цепей

Аннотация

Пусть G-транзитивный граф. Вставим копию графа G вместо каждой вершины бесконечной цепи, добавим ребра между всеми парами вершин из соседних копий. Полученный граф назовем G кратной бесконечной цепью. Определенный таким образом граф является в точности лексикографическим произведением бесконечной цепи на граф G. Пусть n - натуральное число. В статье описаны все совершенные раскраски бесконечных цепей кратных пустому и полному графам на n вершинах в произвольное конечное число цветов.