The square of the 9-hypercube is 14-colorable

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 $χ_{\bar{k}}(n)$. Equivalently, $χ_{\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 \leq χ_{\bar{2}}(9) \leq 14$.

No reviews yet.

No comments yet.