For a given $2k-1$ edge coloring of the complete graph $K_{2k}$, say a Hamiltonian path $P$ is a rainbow path if every color appears exactly once in $P$.

My question is

"For each $2k (k \geq 2)$, is there a proper $2k-1$ edge coloring of $K_{2k}$ with no rainbow paths?"

It is easy to see that every proper edge-coloring of $K_4$ or $K_6$ does not contain any rainbow paths.

For $K_8$, the statement is still true but some proper 7-edge-coloring contains rainbow paths.

When the number of vertices is a power of 2, then the statement is true, but I do not know if it is true for every even number (I don't even know for $2k = 10$).

Here's why the statement is true for $2^k$.

Label the vertices of $K_{2^k}$ by the elements of the group $((Z_2)^k, +)$ and label each edge by the sum(or difference) between two ends. Then the edge-labels give us a proper $2^k-1$ edge coloring, and this coloring does not have any rainbow paths.

  • $\begingroup$ I don't understand. For k=2 and the suggested coloring on K_4, I get a rainbow path of 3 0 2 1, and I get similar paths for larger k. What did I do wrong? Gerhard "Did I Flip A Sign?" Paseman, 2013.01.28 $\endgroup$ – Gerhard Paseman Jan 29 '13 at 4:56
  • $\begingroup$ @Gerhard : For $K_4$, I label the vertices by the elements of $Z_2 \times Z_2$, not $Z_4$. If you use $Z_4$, the edge coloring is not well defined. $\endgroup$ – Ilhee Kim Jan 29 '13 at 5:08

This is an open problem, see the intro of this paper for more details: http://www.renyi.hu/~gyarfas/Cikkek/136_orthogonal.pdf

  • $\begingroup$ Thanks a lot! The paper looks very helpful for better understanding of the problem. $\endgroup$ – Ilhee Kim Jan 29 '13 at 18:14

This is just an overgrown comment with weird formatting:

If a graph coloring has the property that each rainbow (possibly non-Hamiltonian) path must be a cycle, then it is one of your examples. Indeed, let $x_i$ be the permutation of the vertices that sends each vertex to the other vertex along the $i$-colored edge it touches, then each $x_i$ has order $2$, and every permutation of the $x_i$, multiplied together, must fix each vertex, so must be the trivial element. This means that

$x_ix_jx_ix_j=(x_ix_jx_1x_2\dots x_{i-1}x_{i+1} \dots x_{j-1}x_{j+1}\dots x_n) (x_n \dots x_{j+1}x_{j-1} \dots x_{i+1} x_{i-1} \dots x_2x_1x_ix_j)=e$

so the group generated by the $x_i$ is abelian, so is $\mathbb Z_2^n$, and the set of vertices has a transitive faithful action of this group, which must be simply transitive as the group is abelian. So for other sizes, you need to take advantage of the interior vertices.


It seems that one can use a similar trick to that used in your construction on $K_{2^k}$ for any $K_{4n}$: label the vertices by elements of $G = (\mathbb{Z}/2\mathbb{Z} \times \mathbb{Z}/2n\mathbb{Z})$ and assign edge colors by the difference of the two endpoints (EDIT: as noted in Ilhee's comment, this won't be well-defined; am thinking about possible modifications). Since the sum of all the elements of $G$ is the identity, the same argument which shows your coloring of $K_{2^k}$ is rainbow-free applies to this coloring of $K_{4n}$.

Unfortunately this argument fails when we try to use it to label $K_{4n+2}$ by elements of $(\mathbb{Z}/2\mathbb{Z} \times \mathbb{Z}/(2n+1)\mathbb{Z})$ since the sum of the elements of the group is not the identity in this case.

My gut tells me there is some clever way to label the vertices in the $K_{4n+2}$ so as to define colors on the edges which force your condition, but I don't see it; I'll have to think about it some more.

  • $\begingroup$ I think your edge coloring may not be well-defined. For instance, the difference between two vertices (0,1) and (0,2) is either (0,1) or (0,5) in $Z_2 \times Z_6$? For $Z_{2^k}$, we don't have such a problem since $x-y = y-x = x+y$. $\endgroup$ – Ilhee Kim Jan 29 '13 at 4:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.