zbMATH — the first resource for mathematics

Perfect 2-colorings of a hypercube. (Russian, English) Zbl 1164.05348
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.

05C15 Coloring of graphs and hypergraphs
Full Text: EMIS EuDML