Coloring the cube with rainbow cycles

Dhruv Mubayi¹ ; Randall Stading

¹University of Illinois at Chicago

The electronic journal of combinatorics, Tome 20 (2013) no. 2

Résumé

For every even positive integer $k\ge 4$ let $f(n,k)$ denote the minimim number of colors required to color the edges of the $n$-dimensional cube $Q_n$, so that the edges of every copy of the $k$-cycle $C_k$ receive $k$ distinct colors. Faudree, Gyárfás, Lesniak and Schelp proved that $f(n,4)=n$ for $n=4$ or $n>5$. We consider larger $k$ and prove that if $k \equiv 0$ (mod 4), then there are positive constants $c_1, c_2$ depending only on $k$ such that$$c_1n^{k/4} < f(n,k) < c_2 n^{k/4}.$$Our upper bound uses an old construction of Bose and Chowla of generalized Sidon sets. For $k \equiv 2$ (mod 4), the situation seems more complicated. For the smallest case $k=6$ we show that $$3n-2 \le f(n, 6) < n^{1+o(1)}$$ with the lower bound holding for $n \ge 3$. The upper bound is obtained from Behrend's construction of a subset of integers with no three term arithmetic progression.

Détail

DOI : 10.37236/2957

Classification : 05C15, 05C35, 05C38, 05C55
Mots-clés : cube, graph coloring