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

Books Problems Set Theory Combinatorics Extremal Probl/Ramsey Th.
Graph Theory Add.Number Theory Mult.Number Theory Analysis Geometry
Probabability Personalia About Paul Erdös Publication Year Home Page