A Ramsey property of random regular and k‐out graphs. Issue 3 (5th August 2019) - Anastos, Michael; Bal, Deepak
Abstract: 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, 2 r ) 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, 2 r + 1 ) must contain a monochromatic cycle of length at least γ n . We prove an analogous result for random k ‐out graphs.