Zentralblatt MATH
Publications of (and about) Paul Erdös
Zbl.No: 543.05047
Autor: Burr, Stefan A.; Erdös, Paul; Faudree, Ralph J.; Rousseau, C.C.; Schelp, R.H.
Title: Ramsey numbers for the pair sparse graph-path or cycle. (In English)
Source: Trans. Am. Math. Soc. 269, 501-512 (1982).
Review: Let G be a connected graph on n vertices with no more than n(1+\epsilon) edges, and Pk or Ck a path or cycle with k vertices. In this paper we will show that if n is sufficiently large and \epsilon is sufficiently small then for k odd r(G,Ck) = 2n-1. Also, for k \geq 2, r(G,Pk) = max {n+[k/2]-1, n+k-2-\alpha'-\delta}, where \alpha' is the independence number of an appropriate subgraph of G and \delta is 0 or 1 depending upon n,k and \alpha'.
Classif.: * 05C55 Generalized Ramsey theory
Keywords: Ramsey numbers; independence number
© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag