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 Kn is (\bigl(r 2\bigr) + o(1))2\Bigl(n 2\Bigr). This result indicates that almost all Gallai r-colorings of Kn 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 Kn admits the largest number of Gallai 3-colorings among all n-vertex graphs when n is sufficiently large, while for r\geq 4, it is the complete bipartite graph K\lfloor n/2\rfloor,\lceil n/2\rceil. 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. [ABSTRACT FROM AUTHOR]