On size Ramsey number of paths, trees, and circuits. I

Research output: Contribution to journalArticlepeer-review

91 Scopus citations

Abstract

The size Ramsey number ř(G) of a graph G is the smallest integer ř such that there is a graph F of ř edges with the property that any two‐coloring of the edges of F yields a monochromatic copy of G. First we show that the size Ramsey number ř(Pn) of the path Pn of length n is linear in n, solving a problem of Erdös. Second we present a general upper bound on size Ramsey numbers of trees.

Original languageEnglish (US)
Pages (from-to)115-129
Number of pages15
JournalJournal of Graph Theory
Volume7
Issue number1
DOIs
StatePublished - 1983
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Geometry and Topology

Fingerprint

Dive into the research topics of 'On size Ramsey number of paths, trees, and circuits. I'. Together they form a unique fingerprint.

Cite this