On perfect $2$-colorings of the hypercube

K. V. Vorobev ; D. G. Fon-Der-Flaass

Sibirskie èlektronnye matematičeskie izvestiâ, Tome 7 (2010), pp. 65-75

Résumé

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\times 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 $\left({\begin{array}{ll} a b\\c d \end{array}}\right)$ 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 $\left( {\begin{array}{ll} k\cdot a k\cdot b \\ k\cdot c k\cdot d \end{array}}\right)$. For the parameters $\left({\begin{array}{ll} a b\\c d \end{array}}\right)$ satisfying the extra condition $a\ge c-({b,c})$, we find a lower bound on the number of produced colorings which is hyperexponential in $n$.

Détail

Mots-clés : Hypercube
Keywords: perfect coloring, perfect code.