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.

It is unknown if the complete graph K(2n) has a perfect 1-factorization for every n. Analogous to the above, does K(2n) have a 1-factorization in which one factor is perfect?

Submitted by: David Craft

Send comments to dan.archdeacon@uvm.edu and to craft@muskingum.edu