𝔖 Bobbio Scriptorium
✦   LIBER   ✦

An upper bound for the Ramsey numbers r(K3,G)

✍ Scribed by Wayne Goddard; Daniel J. Kleitman

Publisher
Elsevier Science
Year
1994
Tongue
English
Weight
372 KB
Volume
125
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

✦ Synopsis

The Ramsey number r(H, G) is defined as the minimum N such that for any coloring of the edges of the N-vertex complete graph KN in red and blue, it must contain either a ted H or a blue G. In this paper we show that for any graph G without isolated vertices, r(K,, G)< 2qf 1 where G has q edges. In other words, any graph on 2q+ 1 vertices with independence number at most 2 contains every (isolate-free) graph on q edges. This establishes a 1980 conjecture of Harary. The result is best possible as a function of q.

πŸ“œ SIMILAR VOLUMES

An upper bound for some ramsey numbers
An upper bound for some ramsey numbers
✍ Andrew Thomason πŸ“‚ Article πŸ“… 1988 πŸ› John Wiley and Sons 🌐 English βš– 307 KB πŸ‘ 1 views

New upper bounds for the ramsey numbers r ( k , I ) are obtained. In particular it is shown there is a constant A such that The ramsey number r(k, l ) is the smallest integer n, such that any coloring with red and blue of the edges of the complete graph K , of order n yields either a red K , subgra

Upper bounds for ramsey numbers R(3, 3,
Upper bounds for ramsey numbers R(3, 3, ?, 3) and Schur numbers
✍ Wan, Honghui πŸ“‚ Article πŸ“… 1997 πŸ› John Wiley and Sons 🌐 English βš– 81 KB πŸ‘ 2 views

In this paper we show that for n β‰₯ 4, R(3, 3, . . . , 3) < n!( e-e -1 + 3 2 ) + 1. Consequently, a new bound for Schur numbers is also given. Also, for even n β‰₯ 6, the Schur number S n is bounded by S n < n!( e-e -1 + 3 2 ) -n + 2.

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_

An improved upper bound for Ramsey numbe
An improved upper bound for Ramsey number N (3, 3, 3, 3; 2)
✍ Adolfo Sanchez-Flores πŸ“‚ Article πŸ“… 1995 πŸ› Elsevier Science 🌐 English βš– 251 KB

The Ramsey number N(3, 3, 3, 3; 2) is the smallest integer n such that each 4-coloring by edges of the complete graph on n vertices contains monochromatic triangles. It is well known that 51 ~< N(3,3,3,3;2) ~< 65. Here we prove that N(3,3,3,3;2) ~< 64.