Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS

Mobile Device Pairing
Green Open Access
Transactions of the American Mathematical Society
Transactions of the American Mathematical Society
ISSN 1088-6850(online) ISSN 0002-9947(print)


Ramsey numbers for the pair sparse graph-path or cycle

Authors: S. A. Burr, P. Erdős, R. J. Faudree, C. C. Rousseau and R. H. Schelp
Journal: Trans. Amer. Math. Soc. 269 (1982), 501-512
MSC: Primary 05C55
MathSciNet review: 637704
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: Let $ G$ be a connected graph on $ n$ vertices with no more than $ n(1 + \varepsilon )$ edges, and $ {P_k}$ or $ {C_k}$ a path or cycle with $ k$ vertices. In this paper we will show that if $ n$ is sufficiently large and $ \varepsilon $ is sufficiently small then for $ k$ odd

$\displaystyle r(G,\,{C_k}) = 2n - 1.$

Also, for $ k \geqslant 2$,

$\displaystyle r(G,\,{P_k}) = \max \{ n + [k/2] - 1,\,n + k - 2 - \alpha \prime - \delta \} ,$

where $ \alpha \prime $ is the independence number of an appropriate subgraph of $ G$ and $ \delta $ is 0 or $ 1$ depending upon $ n$, $ k$ and $ \alpha \prime $.

References [Enhancements On Off] (What's this?)

Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC: 05C55

Retrieve articles in all journals with MSC: 05C55

Additional Information

PII: S 0002-9947(1982)0637704-5
Article copyright: © Copyright 1982 American Mathematical Society