Edge-coloring of the complete graph without any rainbow paths - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-19T03:28:48Z http://mathoverflow.net/feeds/question/120148 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/120148/edge-coloring-of-the-complete-graph-without-any-rainbow-paths Edge-coloring of the complete graph without any rainbow paths Ilhee Kim 2013-01-28T21:22:44Z 2013-01-30T00:04:41Z <p>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$.</p> <p>My question is</p> <p>"For each $2k (k \geq 2)$, is there a proper $2k-1$ edge coloring of $K_{2k}$ with no rainbow paths?"</p> <p>It is easy to see that every proper edge-coloring of $K_4$ or $K_6$ does not contain any rainbow paths.</p> <p>For $K_8$, the statement is still true but some proper 7-edge-coloring contains rainbow paths.</p> <p>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$).</p> <p>Here's why the statement is true for $2^k$.</p> <p>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. </p> http://mathoverflow.net/questions/120148/edge-coloring-of-the-complete-graph-without-any-rainbow-paths/120156#120156 Answer by Will Sawin for Edge-coloring of the complete graph without any rainbow paths Will Sawin 2013-01-28T22:53:49Z 2013-01-28T22:53:49Z <p>This is just an overgrown comment with weird formatting:</p> <p>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</p> <p>$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$</p> <p>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.</p> http://mathoverflow.net/questions/120148/edge-coloring-of-the-complete-graph-without-any-rainbow-paths/120174#120174 Answer by ARupinski for Edge-coloring of the complete graph without any rainbow paths ARupinski 2013-01-29T04:07:59Z 2013-01-30T00:04:41Z <p>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 <strike>the difference of the two endpoints</strike> (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}$.</p> <p>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.</p> <p>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.</p> http://mathoverflow.net/questions/120148/edge-coloring-of-the-complete-graph-without-any-rainbow-paths/120234#120234 Answer by domotorp for Edge-coloring of the complete graph without any rainbow paths domotorp 2013-01-29T17:28:00Z 2013-01-29T17:28:00Z <p>This is an open problem, see the intro of this paper for more details: <a href="http://www.renyi.hu/~gyarfas/Cikkek/136_orthogonal.pdf" rel="nofollow">http://www.renyi.hu/~gyarfas/Cikkek/136_orthogonal.pdf</a></p>