Gallai 3-colourings of random graphs

Abstract

A Gallai $k$-colouring of a graph $G$ is a colouring of $E(G)$ with $k$ colours that induces no rainbow triangles, that is, a triangle with edges of 3 different colours. We give a first step towards estimating the number of Gallai colourings of the Erdős-Rényi random graph, by proving that for every $\hat{I}´>0$ there are $c$ and $C$ such that with high probability the number of Gallai 3-colourings of $G(n,p)$ is at least $3^{(1-\hat{I}´)\left(\genfrac{}{}{0ex}{}{n}{2}\right)p}$ for $p\le c{n}^{-1/2}$, and at most $2^{(1+\hat{I}´)\left(\genfrac{}{}{0ex}{}{n}{2}\right)p}$ for $p\ge C{n}^{-1/2}$.

12 pages