For any integer k3, let G be a connected graph with n Ω (k⁴) vertices and no more than (1+1ck²) n edges where c>0 is a constant, and Pₖ or Cₖ a path or cycle with k vertices. In this paper we prove that if k is odd then r (G, Cₖ) =2n-1. Moreover, \ r (G, Pₖ) =\n+ k2-1, n+k-2-α'-γ\, \ where α' is the independence number of an appropriate subgraph of G and γ=0 if k-1 divides n+k-3-α' and γ=1 otherwise. Our bound on n in terms of k significantly improves upon the previous bounds n Ω (k^10) (from the first result) and n Ω (k^12) (from the second result) established by Burr, Erdős, Faudree, Rousseau and Schelp (Trans. Amer. Math. Soc. 269 (1982), 501--512). % Moreover, the restriction on the number of edges in G is relaxed. This is the first improvement in over 40 years.
Fan et al. (Wed,) studied this question.