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.

Recommendations

Cites Work

Cited In (5)

Uses Software

This page was built for publication: The chromatic number of the square of the 8-cube