On the size Ramsey number of all cycles versus a path

Deepak Bal, Ely Schudrich

Research output: Contribution to journalArticlepeer-review

Abstract

We say G→(C,Pn) if G−E(F) contains an n-vertex path Pn for any spanning forest F⊂G. The size Ramsey number Rˆ(C,Pn) is the smallest integer m such that there exists a graph G with m edges for which G→(C,Pn). Dudek, Khoeini and Prałat proved that for sufficiently large n, 2.0036n≤Rˆ(C,Pn)≤31n. In this note, we improve both the lower and upper bounds to 2.066n≤Rˆ(C,Pn)≤5.25n+O(1). Our construction for the upper bound is completely different than the one considered by Dudek, Khoeini and Prałat. We also have a computer assisted proof of the upper bound [Figure presented].

Original languageEnglish
Article number112322
JournalDiscrete Mathematics
Volume344
Issue number5
DOIs
StatePublished - May 2021

Keywords

  • Ramsey Theory
  • Size Ramsey
  • Sparse Graphs

Fingerprint Dive into the research topics of 'On the size Ramsey number of all cycles versus a path'. Together they form a unique fingerprint.

Cite this