Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)

 
 

 

The chromatic number of the square of the $ 8$-cube


Authors: Janne I. Kokkala and Patric R. J. Östergård
Journal: Math. Comp. 87 (2018), 2551-2561
MSC (2010): Primary 05C15; Secondary 94B25
DOI: https://doi.org/10.1090/mcom/3291
Published electronically: December 22, 2017
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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.


References [Enhancements On Off] (What's this?)


Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2010): 05C15, 94B25

Retrieve articles in all journals with MSC (2010): 05C15, 94B25


Additional Information

Janne I. Kokkala
Affiliation: Aalto University, School of Electrical Engineering, Department of Communications and Networking, P.O. Box 13000, 00076 Aalto, Finland
Email: janne.kokkala@aalto.fi

Patric R. J. Östergård
Affiliation: Aalto University, School of Electrical Engineering, Department of Communications and Networking, P.O. Box 13000, 00076 Aalto, Finland
Email: patric.ostergard@aalto.fi

DOI: https://doi.org/10.1090/mcom/3291
Received by editor(s): December 2, 2016
Received by editor(s) in revised form: April 15, 2017
Published electronically: December 22, 2017
Additional Notes: The work of the first author was supported by Aalto ELEC Doctoral School, Nokia Foundation, Emil Aaltonen Foundation, and by Academy of Finland Project 289002
The work of the second author was supported in part by Academy of Finland Project 289002.
Article copyright: © Copyright 2017 American Mathematical Society

American Mathematical Society