A Ramsey property of random regular and k‐out graphs. Issue 3 (5th August 2019)

• Record Type: Journal Article
• Authors: Anastos, Michael; Bal, Deepak
• Is Part Of: Journal of graph theory. Volume 93:Issue 3(2020)
• Page Start: 363
• Page End: 371
• Publication Date: 2019-08-05
• Subjects: monochromatic components -- random k‐out graphs -- random regular graphs; Graph theory -- Periodicals; 511
• DOI: 10.1002/jgt.22491
• Languages: English
• ISSNs: 0364-9024

Abstract

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.