ON PERFECT 2-COLORINGS OF THE HYPERCUBE

A vertex coloring of a graph is called perfect if the multiset of colors appearing on the neighbours of any vertex depends only on the color of the vertex. The parameters of a perfect coloring are thus given by a n x n matrix, where n is the number of colors. We give a recursive construction which can produce many different perfect colorings of the hypercube H-n with 2 colors and the parameters parameters ((a)(c) (b)(d)) satisfying the conditions (b, c) = 1, b + c = 2(m), c > 1. In particular, this construction allows one to find many non-isomorphic perfect colorings with the parameters ((k.a)(k.c) (k.b)(k.d)). For the parameters ((a)(c) (b)(d)) satisfying the extra condition a >= c - (b, c), we find a lower bound on the number of produced colorings which is hyperexponential in n.