# 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 .

**Conjecture**.

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.