A coloring of the square of the 8-cube with 13 colors

2015/09/23 by Janne I. Kokkala, Kokkala, Janne I., Patric R. J. Östergård +1
Computer Science · Engineering · #Combinatorics (math.CO) #FOS: Computer and information sciences #FOS: Mathematics #Information Theory (cs.IT) #Interconnection Networks and Systems #graph theory and CDMA systems

paper · pdf · doi:10.48550/arxiv.1509.06913

openalex publication_date 2015/09/23 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Let χ_k(n) be the number of colors required to color the n-dimensional hypercube such that no two vertices with the same color are at a distance at most k. In other words, χ_k(n) is the minimum number of binary codes with minimum distance at least k+1 required to partition the n-dimensional Hamming space. By giving an explicit coloring, it is shown that χ_2(8)=13.

Related

• The square of the 9-hypercube is 14-colorable
• The chromatic number of the square of the 8-cube
• New Results on Two Hypercube Coloring Problems
• The number of colorings of the middle layers of the Hamming cube
• On two q-ary n-cube coloring problems