On a hypercube coloring problem (Q703683)

This paper investigates the \(k\)-distant chromatic number \(\chi_{\overline k}(n)\) of the graph of the \(n\)-dimensional hypercube, which also may be considered as the smallest number of binary codes with minimum distance \(k+1\) forming a partition of the \(n\)-dimensional binary Hamming space. Some lemmas and preparatory theorems present inequalities for \(\chi_{\overline 2}(n)\) and \(\chi_{\overline 3}(n)\); their proofs partially also make use of nonbinary codes. As a main result the asymptotic behaviour of those numbers is given: \(\chi_{\overline 2}(n)\sim n\) and \(\chi_{\overline 3}(n)\sim 2n\) as \(n\) tends to infinity.