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 2n. In studies of the chromatic number of cube-like graphs, the kth power of the n-dimensional hypercube, Qn k, is frequently considered. This coloring problem can be considered in the framework of coding theory, as the graph Qn 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 Qn 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 Q8 2, is here settled by finding a 13-coloring. Such 13-colorings with specific symmetries are further classified.