RAMSEY NUMBERS FOR ALL LINEAR FORESTS
l'hls dnwwr\ m the rltfirmdire d ccrnjccture of Burr and Roberts. I. Introduction , C3vcn graphs If and K, the Ramsey number r(H. K) is the sm:tllest positive integer p such that any graph G on p vertices contains H as a subgraph or its complenrcr!? c contains K as a subgraph. By a result of Ramsey 161, r(H, K) exists for iill graphs H ;ind K. Recently. there has been an increase in interest in the R,irnsey number I( H. K ) for various graphs H and K. An excellent survey article g~tinp the latest results in this direction is given by Burr [ 11. A graph L. is a lincar forest if it is the disjoint union of non~riviuf paths. If i of thtzsc paths havt an odd number of vertices and the union has n vertices. then Iwill be calkd an (II. j) linear forest . The result of this paper is the following t hcorem. Thearem. rf f_) and L .' are (w . j,) and (n:. j?) linear fore.~ts respecfively. then r(L,. I~_-) = IlliiY(fl, + ()I_--j,)/2 -1. nJ -+ (n,j,)/2 -I}. This gcncrali/c\ several known results. Ckrcncskr and Gykfzis in 151 proved that for c)t r n. r(P,. P,,) = nl +-[n/I!] -I. where fk rcpre',cnts a path on k vertices. In 131. Cockayc and Lorimer evaluated r(m ,P,. nr&) where rnP;, represents nz Ifkjoint topic\ of a P-, and Burr and Roberts in [?I determined the diagonal Ramsey numbtzr r(L, L ) for any linear forest I..
2. Notation and preliminstity results
For a graph G, the vertex set will IW denoted by C'(G) and the edge set by E(G).