### 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, 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 language | English |
---|---|

Journal | Journal of Graph Theory |

DOIs | |

State | Accepted/In press - 1 Jan 2019 |

### Fingerprint

### Keywords

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

### Cite this

*Journal of Graph Theory*. https://doi.org/10.1002/jgt.22491

}

**A Ramsey property of random regular and k-out graphs.** / Anastos, Michael; Bal, Deepak.

Research output: Contribution to journal › Article

TY - JOUR

T1 - A Ramsey property of random regular and k-out graphs

AU - Anastos, Michael

AU - Bal, Deepak

PY - 2019/1/1

Y1 - 2019/1/1

N2 - 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.

AB - 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.

KW - monochromatic components

KW - random k-out graphs

KW - random regular graphs

UR - http://www.scopus.com/inward/record.url?scp=85070664105&partnerID=8YFLogxK

U2 - 10.1002/jgt.22491

DO - 10.1002/jgt.22491

M3 - Article

AN - SCOPUS:85070664105

JO - Journal of Graph Theory

JF - Journal of Graph Theory

SN - 0364-9024

ER -