Minimal edge color on constraints Is minimum colors needed to assign colors to edges of complete graph $K_n$ so that every even simple cycle contains an odd number ($>1$) of colors much larger than $(\log n)^\beta$ or $n^{\frac{1}\beta}$ with some fixed $\beta>1$?
What is a good upper bound?
 A: Yes.
Suppose that we did this with $k>1$ colors. For any pair of colors, the graph consisting of edges with these two colors obviously does not contain any even cycle. An even cycle free graph has at most $3(n-1)/2$ edges (see https://math.stackexchange.com/questions/438853/prove-that-the-maximum-number-of-edges-in-a-graph-with-no-even-cycles-is-floor3 ). Then add up these inequalities for any pair of colors, and observe that we counted every edge of $K_n$ exactly $k-1$ times.
$$ \binom{n}{2} (k-1) \leq \binom{k}{2}3(n-1)/2  $$
Thus ignoring constants we have that
$$ n^2k \leq k^2 n $$
$$ n \leq k. $$
Note that $k\leq 3(n-1)/2$ also holds, as if there were more than this amount of colors, we could take an edge from any color, and the resulting graph would have an even cycle, obviously with an even number of colors. Thus roughly we have the bounds 
$$ \frac{2}{3}n \leq k \leq \frac{3}{2} n. $$
A: For sufficiently large $n$ (say $n \geq 20$), there is no edge coloring of $K_n$ which ensures that every 4-cycle gets exactly 3 colors. In particular, the coloring asked in the question is not possible.
(i) There cannot be a monochromatic $P_3$ as this can be completed to a 4-cycle with at most 2 colors. Thus each color class is a star forest.
(ii) If va, vb, vc have the same color 1, then ab, bc and ca must have different colors other than 1.
(iii) From (ii), it is not possible for a vertex to have four edges incident on it of the same color (this would imply that the edges among those 4 neighbors of v are all distinctly colored).
(iv) It is not possible for a vertex to have more than one color repeating on edges incident on it.
(v) Thus for a vertex v except for 3 neighbors, all other edges out of v are distinctly colored. Now consider another vertex w and the edges from v,w to the remaining vertices. We easily get either a monochromatic 4-cycle or a 4-cycle with all distinct colors.
