Edge-colorings of Kn which forbid rainbow cycles

Abstract

The greatest number of colors that can appear on the edges of K_n in a coloring that forbids rainbow A3 's, and thus all rainbow cycles, is n - 1. We charactrize all such colorings (with n - 1 colors): for n ≥ 3 the essentially different such colorings are in natural one-toone correspondence with the full binary trees with n leafs. Related results: (i) if K _n^λ is the multigraph obtained by multiplying each edge of K_n by λ, then the greatest number of colors appearing on the edges of K_n^(λ) in a coloring that forbids rainbow K₃'s is n-1 + (λ- 1)[n/2]; (ii) there is an edge-coloring of K_n using t colors which forbids rainbow K3 's and uses the different colors as close to equally often as possible if and only if t ∈ {1,..., [n/2] }.