New results on hypercube coloring problem from linear codes over Z2k

Abstract

This paper is concerned with the hypercube coloring problem. Let 𝜒 ℓ ⁡ ( 𝑚 ) be the minimum number of colors needed to color the vertices of a hypercube with 2 𝑚 vertices such that every two vertices with Hamming distance ≤ ℓ have different colors. Using linear codes over ℤ 2 𝑘 (the ring of integers modulo 2 𝑘 ) and the generalized Gray map, we establish a connection between the parameters of linear codes over ℤ 2 𝑘 and 𝜒 ℓ ⁡ ( 𝑚 ) . Furthermore, we obtain some new upper bounds on 𝜒 ℓ ⁡ ( 𝑚 ) . In some cases, the new upper bounds are tighter than the previously best known results. In particular, we determine the exact values 𝜒 5 ⁡ ( 1 4 ) = 2 8 and 𝜒 4 ⁡ ( 1 3 ) = 2 7 .