A note on Ramsey numbers for books
- 18 March 2005
- journal article
- research article
- Published by Wiley in Journal of Graph Theory
- Vol. 49 (2) , 168-176
Abstract
The book with n pages Bn is the graph consisting of n triangles sharing an edge. The book Ramsey number r(Bm,Bn) is the smallest integer r such that either Bm ⊂ G or Bn ⊂ G for every graph G of order r. We prove that there exists a positive constant c such that r(Bm,Bn) = 2n + 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 2n/5 are bipartite. © 2005 Wiley Periodicals, Inc. J Graph TheoryKeywords
All Related Versions
This publication has 5 references indexed in Scilit:
- Modern Graph Theory1998
- The maximal number of induced complete bipartite graphsDiscrete Mathematics, 1986
- Strongly regular graphs and finite Ramsey theoryLinear Algebra and its Applications, 1982
- On ramsey numbers for booksJournal of Graph Theory, 1978
- On the connection between chromatic number, maximal clique and minimal degree of a graphDiscrete Mathematics, 1974