The chromatic number of the square of the 8-cube
Loading...
Access rights
openAccess
First published in Math. Comp. 87 (2018), 2551-2561, published by the American Mathematical Society. © 2018 American Mathematical Society.
acceptedVersion
URL
Journal Title
Journal ISSN
Volume Title
A1 Alkuperäisartikkeli tieteellisessä aikakauslehdessä
This publication is imported from Aalto University research portal.
View publication in the Research portal (opens in new window)
View/Open full text file from the Research portal (opens in new window)
Other link related to publication (opens in new window)
View publication in the Research portal (opens in new window)
View/Open full text file from the Research portal (opens in new window)
Other link related to publication (opens in new window)
Date
2018-01-01
Major/Subject
Mcode
Degree programme
Language
en
Pages
11
Series
Mathematics of Computation, Volume 87, issue 313, pp. 2551-2561
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.Description
Keywords
Other note
Citation
Kokkala, J I & Östergård, P R J 2018, ' The chromatic number of the square of the 8-cube ', Mathematics of Computation, vol. 87, no. 313, pp. 2551-2561 . https://doi.org/10.1090/mcom/3291