A Ramsey property of random regular and k-out graphs

Michael Anastos, Deepak Bal

Research output: Contribution to journalArticlepeer-review

1 Scopus citations


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.

Original languageEnglish
Pages (from-to)363-371
Number of pages9
JournalJournal of Graph Theory
Issue number3
StatePublished - 1 Mar 2020


  • monochromatic components
  • random k-out graphs
  • random regular graphs


Dive into the research topics of 'A Ramsey property of random regular and k-out graphs'. Together they form a unique fingerprint.

Cite this