The chromatic number of the square of the 8-cube

Research output: Contribution to journalArticle

Researchers

Research units

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.

Details

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

Download statistics

No data available

ID: 21520738