
Coloring squares of hypercubes (Solved)
If is a simple graph, we let
denote the simple graph with vertex set
and two vertices adjacent if they are distance
in
.

Here , denotes the
-dimensional hypercube, i.e. the graph with vertex set
and two vertices adjacent if they differ in exactly one coordinate. So, the vertices with at most one coordinate equal to
form a clique of size
in
, giving us the easy lower bound
. An independent set in
is precisely an error correcting code, so a proper coloring of this graph may be viewed as a covering of the hypercube with codes. Wan [W] constructed a coloring of
using
many colors, and he conjectures that this is optimal.
Note that contains a subgraph isomorphic to
, so it suffices to prove the conjecture when
is a power of 2. The cases
are rather easy to verify, but
appears to be open.
In his Ph.D. thesis, Ghebleh suggests the stronger conjecture that has circular chromatic number equal to
.
Bibliography
[G] M. Ghebleh, Theorems and Computations in Circular Colourings of Graphs, Ph.D. thesis, Simon Fraser University, 2007.
*[W] P. J. Wan, Near-optimal conflict-free channel set assignments for an optical cluster-based hypercube network. J. Comb. Optim. 1 (1997), no. 2, 179--186. MathSciNet.
* indicates original appearance(s) of problem.
disproved
Actually, the conjecture is disproved by
, obtained independently by Hougardy in 1991 [1] and Royle in 1993 [2, Section 9.7]. Moreover, although not fully determined, it is known that
asymptotically attains the lower bound, as
, proven by Ostergard in 2004 [3].
There are also several results on
for general
, and in particular on
[3,4].
[1] G.M. Ziegler, Coloring Hamming graphs, optimal binary codes, and the 0/1 Borsuk problem in low dimensions, in: H. Alt (Ed.), Computational Discrete Mathematics, Springer, Berlin, 2001, 159-171.
[2] T.R. Jensen, B. Toft, Graph Coloring Problems, Wiley, New York, 1995.
[3] P.R.J. Ostergard, On a Hypercube coloring problem, J. Combin. Theory A 108 (2004), 199-204.
[4] H.Q. Ngo, D.-Z. Du, R.L. Graham, New bounds on a hypercube coloring problem, Inform. Process. Lett. 84 (2002), 265-269.