Edge-coloring of the complete graph without any rainbow paths - MathOverflow

Edge-coloring of the complete graph without any rainbow paths

2013-01-28T21:22:44Z

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.

Answer by Will Sawin for Edge-coloring of the complete graph without any rainbow paths

2013-01-28T22:53:49Z

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.

Answer by ARupinski for Edge-coloring of the complete graph without any rainbow paths

2013-01-29T04:07:59Z

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.

Answer by domotorp for Edge-coloring of the complete graph without any rainbow paths

2013-01-29T17:28:00Z

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