The Ramsey Number for a Forest Versus Disjoint Union of Complete Graphs

Given two graphs G and H, the Ramsey number R(G, H) is the minimum integer N such that any coloring of the edges of K-N in red or blue yields a red G or a blue H. Let chi(G) be the chromatic number of G, and s(G) denote the chromatic surplus of G, the cardinality of a minimum color class taken over all proper colorings of G with chi(G) colors. A connected graph G is called H-good if R(G, H) = (v(G) - 1)(chi(H) - 1) + s(H). Chvztal (J. Graph Theory 1:93, 1977) showed that any tree is K-m-good for m >= 2, where K-m denotes a complete graph with m vertices. Let t H denote the union of t disjoint copies of graph H. Sudarsana et al. (Comput. Sci. 6196, Springer, Berlin, 2010) proved that the n-vertex path Pn is 2K(m)-good for n >= 3 and m >= 2, and conjectured that any n-vertex tree Tn is 2Km-good. In this paper, we confirm this conjecture and prove that T-n is 2K(m)-good for n >= 3 and m >= 2. We also prove a conclusion which yields that Tn is (K-m boolean OR K-l)-good, where K-m boolean OR K-l is the disjoint union of Km and Kl, m >= l >= 2. Furthermore, we extend the Ramsey goodness of connected graphs to disconnected graphs and study the relation between the Ramsey number of the components of a disconnected graph F versus a graph H. We show that if each component of a graph F is H-good, then F is H-good. Our result implies the exact value of R(F, K-m boolean OR K-l), where F is a forest and m, l >= 2.