New bounds on a hypercube coloring problem.
In studying the scalability of optical networks, one problem which arises involves coloring the vertices of the \(n\)-cube with as few colors as possible such that any two vertices whose Hamming distance is at most \(k\) are colored differently. Determining the exact value of \(\chi_{\overline{k}}(n)\), the minimum number of colors needed, appears to be a difficult problem. In this note, we improve the known lower and upper bounds of \(\chi_{\overline{k}}(n)\) and indicate the connection of this coloring problem to linear codes.
scientific article; zbMATH DE number 1856486