A Ramsey Property of Random Regular and $k$-out Graphs

Abstract

In this note we consider a Ramsey property of random $d$-regular graphs, $\mathcal{G}(n,d)$. Let $r\ge 2$ be fixed. Then w.h.p. the edges of $\mathcal{G}(n,2r)$ can be colored such that every monochromatic component has size $o(n)$. On the other hand, there exists a constant $\gamma >0$ such that w.h.p., every $r$-coloring of the edges of $\mathcal{G}(n,2r+1)$ must contain a monochromatic cycle of length at least $\gamma n$. We prove an analogous result for random $k$-out graphs.

8 pages