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.