New Bounds on a Hypercube Coloring Problem

Abstract

On studying the scalability of optical networks, one problem arising is to color 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_k(n)$, the minimum number of colors needed, is a difficult problem.

In this paper, we improve the lower and upper bounds of $chi_k(n)$ and indicate the connection of this coloring problemto linear codes.