���-���-����� �. �.
����������� 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)