Bipartite perfect colorings of the infinite square grid: twin colors and the covering case

Совершенная раскраска графа $G$ – это функция $f$ из множества вершин на некоторое конечное множество (цветов) такая, что каждый узел цвета $i$ имеет ровно $S(i,j)$ соседей цвета $j$, где $S(i,j)$ – константы, образующие матрицу $S$, называемую факторной. Если $S$ – матрица смежности некоторого простого графа $T$ на множестве цветов, то $f$ называется накрытием целевого графа $T$ накрывающим графом $G$. Мы характеризуем все накрытия бесконечной квадратной решеткой в случае, когда целевой граф является двудольным, доказывая, что каждая такая раскраска либо орбитная (то есть соответствует разбиению на орбиты под действием некоторой подгруппы группы автоморфизмов графа), либо имеет цвета-близнецы (то есть, два цвета, отождествление которых сохраняет совершенство окраски). Случай близнецов классифицируется отдельно.