Um limiar para a quantidade de 3-colorações de Gallai em G(n,p)

Abstract

We study the number of Gallai 3-colorings in the Erdös-Rényi random graph, G(n, p). A Gallai 3-coloring of a graph is a coloring of its edges with colors {1,2,3} such that there is no rainbow triangle, that is, a triangle with edges of 3 distinct colors. It is trivial that for any graph with E edges, the number of Gallai 3-colorings is between 2E and 3E. Now, let E be the random variable for the number of edges in G(n, p). We show that for every δ > 0 there are constants cand C such that, asymptotically almost surely, for p < cn−1/2, the number of Gallai 3-coloring of G(n, p) is at least 3(1−δ)E; and for p > Cn−1/2 this number is at most 2(1+δ)E.