The square of the 9-hypercube is 14-colorable

Abstract

The $n$-hypercube, denoted by $Q_n$, has a vertex for each bit string of length $n$ with two vertices adjacent whenever their Hamming distance is one. The minimum number of colors needed to color $Q_n$ such that no two vertices at a distance at most $k$ receive the same color is denoted by ${\chi }_{\bar{k}}(n)$. Equivalently, ${\chi }_{\bar{k}}(n)$ denotes the minimum number of binary codes with minimum distance at least $k+1$ required to partition the $n$-dimensional Hamming space. Using a computer search, we improve upon the known upper bound for $n=9$ by showing that $13\le {\chi }_{\bar{2}}(9)\le 14$.

3 pages