New results on two hypercube coloring problems

In this paper, we study the following two hypercube coloring problems: given nn and dd, find the minimum number of colors, denoted as χd′(n) (resp. χd(n)χd(n)), needed to color the vertices of the nn-cube such that any two vertices with Hamming distance at most dd (resp. exactly dd) have different colors. These problems originally arose in the study of the scalability of optical networks. Using methods in coding theory, we show that χ5′(2r+1)=4r+1 for any odd number r≥3r≥3, and give two upper bounds on χd(n)χd(n). The first upper bound improves on that of Kim, Du and Pardalos. The second upper bound improves on the first one for small nn. Furthermore, we derive an inequality on χd(n)χd(n) and χd′(n).