✳flâneur — a map of the web's best reading

[2604.04115] Gallai 3-colourings of random graphs

arxiv.org · 92 words · saved by 1 readers

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 $\delta > 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-\delta)\binom{n}{2}p}$ for $p \leq cn^{-1/2}$, and at most $2^{(1+\delta)\binom{n}{2}p}$ for $p \geq Cn^{-1/2}$.

Gallai 3-colourings of random graphs 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}$.

Explore this link on the map →

saved by

related reading