The typical structure of Gallai colorings and their extremal graphs

An edge coloring of a graph G is a Gallai coloring if it contains no rainbow triangle. We show that the number of Gallai r-colorings of K_n is ((^r ₂) + o(1))2(ⁿ ₂). This result indicates that almost all Gallai r-colorings of K_n use only 2 colors. We also study the extremal behavior of Gallai r-colorings among all n-vertex graphs. We prove that the complete graph K_n admits the largest number of Gallai 3-colorings among all n-vertex graphs when n is sufficiently large, while for r ≥ 4, it is the complete bipartite graph K_[n/2],[n/2]. Our main approach is based on the hypergraph container method, developed independently by Balogh, Morris, and Samotij as well as by Saxton and Thomason, together with some stability results.