Zentralblatt MATH

Publications of (and about) Paul Erdös

Zbl.No:  383.05027
Autor:  Erdös, Paul; Faudree, Ralph J.; Rousseau, C.C.; Schelp, R.H.
Title:  On cycle-complete graph Ramsey numbers. (In English)
Source:  J. Graph Theory 2, 53-64 (1978).
Review:  Given graphs G1 and G2, there exists an integer r such that if q is any integer greater than or equal to r, if E1,E2 is any partition of the edge set of Kq (the complete graph on q vertices) and if H1 and H2 are the subgraphs of Kq with these edge sets, then either H1 contains a subgraph isomorphic to G1 or H2 contains a subgraph isomorphic to G2. The Ramsey number r(G1,G2) is the smallest integer with the obove property. In this paper the authors consider the case where G1 is Cm, a circuit of length m, and G2 is Kn. The main result is: for all m \geq 3 and n \geq 2, r(Cm,Kn) \leq {(m-2)(n1/k+2)+1}(n-1), where {x} denotes the least inter \geq x and k denotes the integer part of (m-1)/2. Additional results are given for special values of m or n.
Reviewer:  J.E.Graver
Classif.:  * 05C55 Generalized Ramsey theory

© 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