Premium
A Ramsey property of random regular and k ‐out graphs
Author(s) -
Anastos Michael,
Bal Deepak
Publication year - 2020
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.22491
Subject(s) - mathematics , monochromatic color , combinatorics , ramsey's theorem , ramsey theory , property (philosophy) , constant (computer programming) , random graph , discrete mathematics , order (exchange) , graph , computer science , philosophy , epistemology , finance , economics , programming language , botany , biology
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.