𝔖 Bobbio Scriptorium
✦   LIBER   ✦

A note on Ramsey numbers for books

✍ Scribed by Vladimir Nikiforov; Cecil C. Rousseau

Publisher
John Wiley and Sons
Year
2005
Tongue
English
Weight
87 KB
Volume
49
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

The book with n pages B~n~ is the graph consisting of n triangles sharing an edge. The book Ramsey number r(B~m~,B~n~) is the smallest integer r such that either B~m~ ⊂ G or B~n~ ⊂ G for every graph G of order r. We prove that there exists a positive constant c such that r(B~m~,B~n~) = 2__n__ + 3 for all n ≥ cm. Our proof is based mainly on counting; we also use a result of Andrásfai, Erdős, and Sós stating that triangle‐free graphs of order n and minimum degree greater than 2__n__/5 are bipartite. © 2005 Wiley Periodicals, Inc. J Graph Theory

📜 SIMILAR VOLUMES

On ramsey numbers for books
On ramsey numbers for books
✍ C. C. Rousseau; J. Sheehan 📂 Article 📅 1978 🏛 John Wiley and Sons 🌐 English ⚖ 479 KB

For n = 1, 2, . . . , let 6, = K2+ K,,. We pose the problem of determining the Ramsey numbers r(&, B,) and demonstrate that in many cases critical colorings are available from known examples of strongly regular graphs.

A note on constructive methods for ramse
A note on constructive methods for ramsey numbers
✍ F. R. K. Chung 📂 Article 📅 1981 🏛 John Wiley and Sons 🌐 English ⚖ 227 KB 👁 1 views

## Abstract Let __r(k__) denote the least integer __n__‐such that for any graph __G__ on __n__ vertices either __G__ or its complement G contains a complete graph __K__~k~ on __k__ vertices. in this paper, we prove the following lower bound for the Ramsey number __r(k__) by explicit construction: _

On irredundant Ramsey numbers for graphs
On irredundant Ramsey numbers for graphs
✍ Johannes H. Hattingh 📂 Article 📅 1990 🏛 John Wiley and Sons 🌐 English ⚖ 248 KB

## Abstract The irredundant Ramsey number __s(m, n)__ is the smallest p such that in every two‐coloring of the edges of __K~p~__ using colors red (__R__) and blue (__B__), either the blue graph contains an __m__‐element irredundant set or the red graph contains an __n__‐element irredundant set. We

On Book-Complete Graph Ramsey Numbers
On Book-Complete Graph Ramsey Numbers
✍ Yusheng Li; C.C. Rousseau 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 274 KB

It is shown that a graph of order N and average degree d that does not contain the book B m =K 1 +K 1, m as a subgraph has independence number at least Nf (d ), where f (x)t(log xÂx) (x Ä ). From this result we find that the book-complete graph Ramsey number satisfies r(B m , K n ) mn 2 Âlog(nÂe). I

On ramsey-tuŕan numbers for 3-graphs
On ramsey-tuŕan numbers for 3-graphs
✍ A. F. Sidorenko 📂 Article 📅 1992 🏛 John Wiley and Sons 🌐 English ⚖ 255 KB

## Abstract For every __r__‐graph __G__ let π(__G__) be the minimal real number ϵ such that for every ϵ < 0 and __n__ ϵ __n__~0~(λ, __G__) every __R__‐graph __H__ with __n__ vertices and more than (π + ϵ)(nr) edges contains a copy of __G__. The real number λ(__G__) is defined in the same way, addin