Edge Coloring the n-Cube

The usual minimal edge coloring of the *n*-cube has the property that any two colors
form a subgraph with each component a 4-cycle. We desire an opposite extreme.

**Conjecture:*** For each integer n there is a coloring of the edges of the n-cube
with n colors, one being black, such that the black edges together with the edges of any other
color induce a Hamiltonian cycle. *

This is trivial for *n *= 2 and easy for *n* = 3. I have two such colorings of
the 4-cube, one of them very nicely symmetric. It is not clear to me how to generalize it.

This kind of edge coloring of the cubes (and graphs in general) would lead to an improvement of existing genus results for joins and compositions of these graphs.

A proper *n*-edge-coloring of an n-regular graph is also called a
*1-factorization*. A 1-factorization is *perfect* if the union of any two 1-factors
(color classes) is a Hamilitonian cycle. A stronger conjecture would be that every
*n*-cube has a perfect 1-factorization.

In an earlier version of this page Dan Archdeacon stated that it was unknown if the
complete graph *K(2n)* has a perfect 1-factorization for every *n*. I asked if
analogous to the above, does *K(2n)* have a 1-factorization in which one factor is
perfect?

In the paper "Sequencings and Starters" by B.A.Anderson, Pacific Journal of Mathematics, 64, n.1 (1976), the author takes a symmetric sequenceable group G of order 2n (for example the cyclic group) and construct a 1-factorization of the complete graph K(2n+2). He identifies the vertices of the graph with the elements of G plus two ideal elements, and constructs the 1-factors via the symmetric sequence. The obtained 1-factorization has a perfect 1-factor.

Dan Archdeacon believes that Gloria Rinaldi and Giuseppe Mazzuoccolo University of Modena
and Reggio Emilia, Italy, have done further work on this topic: finding a "special" 1-factor
whose union with all other 1-factors have a specific structure (not necessarily Hamiltonian).
The interested reader should contact: *rinaldi.gloria@unimore.it * or
*mazzuoccolo.giuseppe@unimore.it *

Dinitz, Dukes, and Stinson wrote "Sequentially perfect and uniform one-factorizations of the
complete graph", Elec. Jour. of Combinatorics, 11 (2004). They found a 1-factorization in
which
1-factors *i* and *i+1* form a Hamiltonian cycle for each *i* and each
*K(2n)*.

Submitted by: David Craft

Send comments to *craft@muskingum.edu*

August, 1995.
or to *dan.archdeacon@uvm.edu*.
Last edited November, 2005.