New Results on Two Hypercube Coloring Problems

2010/01/13 by Fang‐Wei Fu, Fu, Fang-Wei, San Ling +3 · 1 citation
Engineering · Computer Science · #graph theory and CDMA systems #Advanced Graph Theory Research #Coding theory and cryptography

paper · pdf · doi:10.48550/arxiv.1001.2209

Abstract

In this paper, we study the following two hypercube coloring problems: Given n and d, find the minimum number of colors, denoted as χ'_d(n) (resp. χ_d(n)), needed to color the vertices of the n-cube such that any two vertices with Hamming distance at most d (resp. exactly d) have different colors. These problems originally arose in the study of the scalability of optical networks. Using methods in coding theory, we show that χ'₄(2^r+1-1)=2^2r+1, χ'₅(2^r+1)=4^r+1 for any odd number r≥3, and give two upper bounds on χ_d(n). The first upper bound improves on that of Kim, Du and Pardalos. The second upper bound improves on the first one for small n. Furthermore, we derive an inequality on χ_d(n) and χ'_d(n).

Cited by

• Quantum Chromatic Number of Subgraphs of Orthogonality Graphs and the Distance-2 Hamming Graph

Related

• On two q-ary n-cube coloring problems
• A coloring of the square of the 8-cube with 13 colors
• The square of the 9-hypercube is 14-colorable
• The number of colorings of the middle layers of the Hamming cube
• The chromatic number of the square of the 8-cube