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