The number of Gallai k-colorings of complete graphs

Abstract

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 $((\genfrac{}{}{0ex}{}{k}{2})+o_n(1))2^{\left(\genfrac{}{}{0ex}{}{n}{2}\right)}$. 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})$.

11 pages