Monotone chromatic index of oriented hypercube

81 Views Asked by At

Edge coloring is right if any adjacent edges have different color. Right edge coloring is monotone if a color of an edge outcoming from vertex $v$, is bigger than the color of any incoming edge into vertex $v$. The chromatic index is a minimal number of colors among all monotone colorings. The problem is to estimate the range of chromatic indexes of oriented variants of the hypercube. I proved that it is >= n and it is reachable. Also proved that $\ge 2^n - 1$( consider Hamiltonian path). I am pretty sure it is also $\le 2^n-1$, but I couldn't prove it, any ideas are welcomed.