A coloring problem on the \(n\)-cube (Q1570845)

Let \(\chi _{k}(n)\) be the minimum number of colors needed to color the vertices of the \(n\)-cube so that every two vertices with Hamming distance \(\leq k\) have different colors. In this paper it is shown that \(2n\leq \chi _{3}(n)\leq 2^{\lceil \log_{2}n\rceil +1}\) and upper and lower bounds on \(\chi _{k}(n)\) for general \(k\) are provided. This coloring problem on the \(n\)-cube arises in the study of scalability of optical networks.