𝔖 Bobbio Scriptorium
✦   LIBER   ✦

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

✍ Scribed by JóZsef Beck

Book ID
102892089
Publisher
John Wiley and Sons
Year
1983
Tongue
English
Weight
622 KB
Volume
7
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

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 ř(P~n~) of the path P~n~ 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.

📜 SIMILAR VOLUMES

On the Ramsey number of trees versus gra
On the Ramsey number of trees versus graphs with large clique number
✍ Ronald J. Gould; Michael S. Jacobson 📂 Article 📅 1983 🏛 John Wiley and Sons 🌐 English ⚖ 335 KB

Chvatal established that r(T,, K,,) = (m -1 ) ( n -1 ) + 1, where T, , , is an arbitrary tree of order m and K, is the complete graph of order n. This result was extended by Chartrand, Gould, and Polimeni who showed K, could be replaced by a graph with clique number n and order n + 5 provided n 2 3

An upper bound on the ramsey number R(K3
An upper bound on the ramsey number R(K3, G) depending only on the size of the graph G
✍ A. F. Sidorenko 📂 Article 📅 1991 🏛 John Wiley and Sons 🌐 English ⚖ 135 KB 👁 1 views

## Abstract Harary stated the conjecture that for any graph __G__ with __n__ edges and without isolated vertices __r__(__K__~3~,__G__) ⩽ 2__n__ + 1. Erdös, Faudree, Rousseau, and Schelp proved that __r__(__K__~3~,__G__) ⩽ ⌈8/3__n__⌉. Here we prove that __r__(__K__~3~,__G__) ⩽ ⌊5/2__n__⌋ −1 for __n_