ON THE RAMSEY NUMBERS OF NON-STAR TREES VERSUS CONNECTED GRAPHS OF ORDER SIX.

This paper completes our studies on the Ramsey number r(Tn,G) for trees Tn of order n and connected graphs G of order six. If Χ(G) ≥ 4, then the values of r(Tn,G) are already known for any tree Tn. Moreover, r(Sn,G), where Sn denotes the star of order n, has been investigated in case of Χ(G) ≤ 3. If Χ(G) = 3 and G 6= K2,2,2, then r(Sn,G) has been determined except for some G and some small n. Partial results have been obtained for r(Sn,K2,2,2) and for r(Sn,G) with Χ(G) = 2. In the present paper we investigate r(Tn,G) for non-star trees Tn and Χ(G) ≤ 3. Especially, r(Tn,G) is completely evaluated for any non-star tree Tn if Χ(G) = 3 where G 6 = K2,2,2, and r(Tn,K2,2,2) is determined for a class of trees Tn with small maximum degree. In case of Χ(G) = 2, r(Tn,G) is investigated for Tn = Pn, the path of order n, and for Tn = B2,n-2, the special broom of order n obtained by identifying the centre of a star S3 with an end-vertex of a path Pn-2. Furthermore, the values of r(B2,n-2, Sm) are determined for all n and m with n ≥ m- 1. As a consequence of this paper, r(F,G) is known for all trees F of order at most five and all connected graphs G of order at most six. [ABSTRACT FROM AUTHOR]