A coloring problem on the n-cube

In this paper, we consider a coloring problem on the n-cube that arises in the study of scalability of optical networks. Let chi((k) over bar)(n) be t he minimum number of colors needed to color the vertices of the n-cube so t hat every two vertices with Hamming distance less than or equal to k have d ifferent colors. We show that for k = 3, 2n less than or equal to chi((3) o ver bar)(n) less than or equal to 2([log2 n]+1). We also provide upper and lower bounds on chi((k) over bar)(n) for general k. (C) 2000 Elsevier Scien ce B.V. All rights reserved.