New Bounds on a Hypercube Coloring Problem

Date of Submission: 
March 3, 1999
Report Number: 
99-010
Report PDF: 
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_{ar{k}}(n)$, the minimum number of colors needed, is a difficult problem. In this paper, we improve the lower and upper bounds of$chi_{ar{k}}(n)$ and indicate the connection of this coloring problemto linear codes.