Ramsey numbers of trees and unicyclic graphs versus fans

The generalized Ramsey number R(H, K) is the smallest positive integer n such that for any graph G with n vertices either G contains H as a subgraph or its complement (G) over bar contains K as a subgraph. Let T-n, be a tree with n vertices and F-m be a fan with 2m + 1 vertices consisting of m triangles sharing a common vertex. We prove a conjecture of Zhang, Broersma and Chen form >= 9 that R(T-n, F-m) = 2n - 1 for all n >= m(2) - m + 1. Zhang, Broersma and Chen showed that R(S-n, F-m) >= 2n for n <= m2 m where.s(n) is a star on n vertices, implying that the lower bound we show is in some sense tight. We also extend this result to unicyclic graphs UCn, which are connected graphs with n vertices and a single cycle. We prove that R(UCn, F-m) = 2n -1 for all n >= m(2-) - m + 1 where m >= 18. In proving this conjecture and extension, we present several methods for embedding trees in graphs, which may be of independent interest. Published by Elsevier B.V.