On a hypercube coloring problem

JOURNAL OF COMBINATORIAL THEORY SERIES A

卷:108

Article

Östergard, PRJ

关键词: binary code;    chromatic number;    hypercube;    vertex coloring;   

DOI  :  10.1016/j.jcta.2004.06.010

来源: Elsevier

【 摘 要 】

Let chi(k)(n) denote the minimum number of colors necessary to color the n-dimensional hypercube so that no two vertices that are at a distance at most k from each other get the same color. In other words, this is the smallest number of binary codes with minimum distance k + 1 that form a partition of the n-dimensional binary Hamming space. It is shown that chi(2)(n) similar to n and chi(3)(n) similar to 2n as n tends to infinity. (C) 2004 Elsevier Inc. All rights reserved.

【 授权许可】

Free