Distribution of colors in Gallai colorings

András Gyárfás; Dömötör Pálvölgyi; Balázs Patkós; Matthew Wales

doi:10.1016/j.ejc.2020.103087

paper

Distribution of colors in Gallai colorings

arXiv:1903.04380 · doi:10.1016/j.ejc.2020.103087

Abstract

A Gallai coloring is an edge coloring that avoids triangles colored with three different colors. Given integers $e_{1} \geq e_{2} \geq \dots \geq e_{k}$ with $\sum_{i = 1}^{k} e_{i} = (2 n)$ 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} \leq 1$ and $k \leq ⌊ n /2 ⌋$ . We prove that for any integer $k \geq 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_{1} \leq \dots \leq e_{k}$ satisfying $\sum_{i = 1}^{k} e_{i} = (2 n)$ , if and only if $n \geq g (k)$ . We show that $g (3) = 5$ , $g (4) = 8$ , and $2 k - 2 \leq g (k) \leq 8 k^{2} + 1$ for every $k \geq 3$ .