A Note on Algebraic Hypercube Colorings

An L(1, 1)-coloring of the n-dimensional hypercube Q_n assigns nodes of Q_n which are at distance les 2 with different colors. Such colorings find application, e.g., in frequency assignment in wireless networks and data distribution in parallel memory systems. Let chi₂ macr(Q_n) be the minimum number of colors used in any L(1, 1)-coloring. Finding the exact value of chi₂ macr(Q_n) is still an open problem, and only 2-approximate solutions are currently known. In this paper we expose some connections between group theory and the L(1, 1)-coloring problem. Namely, we unfold the algebraic structure on which the best available L(1, 1)-coloring algorithms of Q_n are based, thus giving a group theoretic flavour to existing L(1, 1)-colorings. We show that identifying groups such that the inverse of each element is the element itself yields a simple and efficient way to obtain L(1, 1)-colorings of the hypercube. We also prove that such colorings are balanced and that every coloring algorithm based on this algebraic structure cannot improve the current upper bound on chi₂ macr(Q_n), independently of the choice of the group operation.