{"id":"arxiv/2604.04115","url":"https://arxiv.org/abs/2604.04115","tags":["math.CO"],"score":0,"title":"Gallai 3-colourings of random graphs","domain":"math.CO","source":"arxiv","authors":["Fabrício S. Benevides","Rubens C. S. Monteiro","Guilherme O. Mota"],"reviews":0,"subject":"math.CO","summary":"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 $δ> 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-δ)\\binom{n}{2}p}$ for $p \\leq cn^{-1/2}$, and at most $2^{(1+δ)\\binom{n}{2}p}$ for $p \\geq Cn^{-1/2}$.","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-04-05","reactions":{}}