A Gallai coloring is an edge coloring that avoids triangles colored with
three different colors. Given integers $e_1\ge e_2 \ge \dots \ge e_k$ with
$\sum_{i=1}^ke_i={n \choose 2}$ for some $n$, does there exist a Gallai
$k$-coloring of $K_n$ with $e_i$ edges in color $i$? In this paper, we give
several sufficient conditions and one necessary condition to guarantee a
positive answer to the above question. In particular, we prove the existence of
a Gallai-coloring if $e_1-e_k\le 1$ and $k \le \lceil n/2\rceil$. We prove that
for any integer $k\ge 3$ there exists a smallest $m$ (denoted by $g(k)$) such
that if $\sum_{i=1}^ke_i={n \choose 2}$ for some $n\ge m$, then there exists a
Gallai coloring of $K_n$ with $e_i$ edges in color $i$, but for every $3\le
n