The chromatic number of the square of the 8-cube

Janne I. Kokkala, Patric R.J. Östergård

Research output: Contribution to journalArticleScientificpeer-review

2 Citations (Scopus)
103 Downloads (Pure)

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.

Original languageEnglish
Pages (from-to)2551-2561
Number of pages11
JournalMathematics of Computation
Volume87
Issue number313
DOIs
Publication statusPublished - 1 Jan 2018
MoE publication typeA1 Journal article-refereed

Fingerprint

Dive into the research topics of 'The chromatic number of the square of the 8-cube'. Together they form a unique fingerprint.

Cite this