A Ramsey property of random regular and k-out graphs

Michael Anastos, Deepak Bal

Research output: Contribution to journalArticle

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 languageEnglish
Pages (from-to)363-371
Number of pages9
JournalJournal of Graph Theory
Volume93
Issue number3
DOIs
StateAccepted/In press - 1 Jan 2019

Fingerprint

Order Component
Graph in graph theory
Regular Graph
Colouring
Cycle

Keywords

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

Cite this

Anastos, Michael ; Bal, Deepak. / A Ramsey property of random regular and k-out graphs. In: Journal of Graph Theory. 2020 ; Vol. 93, No. 3. pp. 363-371.
@article{15e2fdee7587479da79e56a33238de74,
title = "A Ramsey property of random regular and k-out graphs",
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.",
keywords = "monochromatic components, random k-out graphs, random regular graphs",
author = "Michael Anastos and Deepak Bal",
year = "2019",
month = "1",
day = "1",
doi = "10.1002/jgt.22491",
language = "English",
volume = "93",
pages = "363--371",
journal = "Journal of Graph Theory",
issn = "0364-9024",
publisher = "Wiley-Liss Inc.",
number = "3",

}

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

In: Journal of Graph Theory, Vol. 93, No. 3, 01.03.2020, p. 363-371.

Research output: Contribution to journalArticle

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

VL - 93

SP - 363

EP - 371

JO - Journal of Graph Theory

JF - Journal of Graph Theory

SN - 0364-9024

IS - 3

ER -