On a hypercube coloring problem (Q703683): Difference between revisions
From MaRDI portal
Latest revision as of 17:12, 7 June 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On a hypercube coloring problem |
scientific article |
Statements
On a hypercube coloring problem (English)
0 references
11 January 2005
0 references
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.
0 references
binary code
0 references
chromatic number
0 references
hypercube
0 references
vertex coloring
0 references
0 references