

Title: 
The chromatic number of the square of the 8cube 
Author(s): 
Kokkala, Janne I.
;
Östergård, Patric R.J.

Date: 
20180101 
Language: 
en 
Pages: 
11 25512561 
Department: 
Department of Communications and Networking 
Series: 
Mathematics of Computation, Volume 87, issue 313 
ISSN: 
00255718 
DOInumber: 
10.1090/mcom/3291

Subject: 
Algebra and Number Theory, Computational Mathematics, Applied Mathematics, 111 Mathematics

Keywords: 
Algebra and Number Theory, Computational Mathematics, Applied Mathematics, 111 Mathematics

» Show full item record


Citation:
Kokkala , J I & Östergård , P R J 2018 , ' The chromatic number of the square of the 8cube ' Mathematics of Computation , vol 87 , no. 313 , pp. 25512561 . DOI: 10.1090/mcom/3291

Abstract:
A cubelike graph is a Cayley graph for the elementary abelian group of order 2n. In studies of the chromatic number of cubelike graphs, the kth power of the ndimensional 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 ndimensional 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 13coloring. Such 13colorings with specific symmetries are further classified.


Permanent link to this item:
http://urn.fi/URN:NBN:fi:aalto201806183301
