A Ramsey property of random regular and k‐out graphs.

In this study we consider a Ramsey property of random d‐regular graphs, G(n,d). Let r≥2 be fixed. Then w.h.p. the edges of G(n,2r) can be colored such that every monochromatic component has order o(n). On the other hand, there exists a constant γ>0 such that w.h.p., every r‐coloring of the edges of G(n,2r+1) must contain a monochromatic cycle of length at least γn. We prove an analogous result for random k‐out graphs. [ABSTRACT FROM AUTHOR]