In this paper, we study the following two hypercube coloring problems: given   n     n        and   d     d       , find the minimum number of colors, denoted as              χ    d    ′     (  n  )         (resp.   χ d (n)       χ    d     (  n  )        ), needed to color the vertices of the   n     n       -cube such that any two vertices with Hamming distance at most   d     d        (resp. exactly   d     d       ) have different colors. These problems originally arose in the study of the scalability of optical networks. Using methods in coding theory, we show that              χ    5    ′     (    2    r  +  1    )   =    4    r  +  1          for any odd number   r≥3     r  ≥  3       , and give two upper bounds on   χ d (n)       χ    d     (  n  )        . The first upper bound improves on that of Kim, Du and Pardalos. The second upper bound improves on the first one for small   n     n       . Furthermore, we derive an inequality on   χ d (n)       χ    d     (  n  )         and              χ    d    ′     (  n  )        .
['Fang-Wei Fu', 'San Ling', 'Chaoping Xing']
New Results on Two Hypercube Coloring Problems