Фон-Дер-Флаас Д. Г.
Совершенные 2-раскраски гиперкуба

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

Fon-Der-Flaass D. G. 
Perfect 2-colorings of a hypercube

A coloring of the vertices of a graph is called perfect if the multiset of colors of all neighbors of a vertex depends only on its own color. We study the possible parameters of perfect 2-colorings of the n-dimensional cube. Some necessary conditions are obtained for existence of such colorings. A new recursive construction of such colorings is found, which produces colorings for all known and infinitely many new parameter sets.

Полный текст статьи / Full texts:

• PDF file (160 KB)
• PostScript file (693 KB)