The chromatic number of the square of the 8-cube

Abstract

A cube-like graph is a Cayley graph for the elementary abelian group of order $2^n$. In studies of the chromatic number of cube-like graphs, the $k$th power of the $n$-dimensional hypercube, $Q_n^k$, is frequently considered. This coloring problem can be considered in the framework of coding theory, as the graph $Q_n^k$ can be constructed with one vertex for each binary word of length $n$ and edges between vertices exactly when the Hamming distance between the corresponding words is at most $k$. Consequently, a proper coloring of $Q_n^k$ corresponds to a partition of the $n$-dimensional binary Hamming space into codes with minimum distance at least $k+1$. The smallest open case, the chromatic number of $Q_8^2$, is here settled by finding a 13-coloring. Such 13-colorings with specific symmetries are further classified.

15 pages. Preliminary results of this research were reported in arXiv:1509.06913