Perfect 2-colorings of a hypercube. (Russian, English) Zbl 1164.05348

Fon-Der-Flaass, D. G.

Sib. Mat. Zh. 48, No. 4, 923-930 (2007); translation in Sib. Math. J. 48, No. 4, 740-745 (2007).

Summary: 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.

MSC:

05C15

Coloring of graphs and hypergraphs

Keywords:

hypercube; coloring; perfect code