Constrained Ramsey numbers of graphs

Given two graphs G and H , let f ( G , H ) denote the minimum integer n such that in every coloring of the edges of K n , there is either a copy of G with all edges having the same color or a copy of H with all edges having different colors. We show that f ( G , H ) is finite iff G is a star or H is acyclic. If S and T are trees with s and t edges, respectively, we show that 1+ s ( t −2)/2≤ f ( S , T )≤( s −1)( t 2 +3 t ). Using constructions from design theory, we establish the exact values, lying near ( s −1)( t −1), for f ( S,T ) when S and T are certain paths or star‐like trees. © 2002 Wiley Periodicals, Inc. J Graph Theory 42: 1–16, 2003