An edge coloring of the $n$-vertex complete graph, $K_n$, is a Gallai coloring if it does not contain any rainbow triangle, that is, a triangle whose edges are colored with three distinct colors. We prove that for $n$ large and every $k$ with $k\le 2^{ n/4300}$, the number of Gallai colorings of $K_n$ that use at most $k$ given colors is $(\binom{ k}{ 2}+o_n(1))\,2^{ \binom{ n}{ 2}}$. Our result is asymptotically best possible and implies that, for those $k$, almost all Gallai $k$-colorings use only two colors. However, this is not true for $k \ge \Omega (2^{ 2n})$.
Categories: math.CO