A Gallai coloring is an edge coloring that avoids triangles colored with three different colors. Given integers $e_1ge 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_kle 1$ and $k le lfloor n/2rfloor$. We prove that for any integer $kge 3$ there is a (unique) integer $g(k)$ with the following property: there exists a Gallai $k$-coloring of $K_n$ with $e_i$ edges in color $i$ for every $e_1ledots le e_k$ satisfying $sum_{i=1}^ke_i={nchoose 2}$, if and only if $nge g(k)$. We show that $g(3)=5$, $g(4)=8$, and $2k-2le g(k)le 8k^2+1$ for every $kge 3$.
Download