Constrained Ramsey numbers of graphs
by
Robert E. Jamison
Clemson University
Coauthors: Tao Jiang and Alan C.H. Ling (both of Michigan Technological University)

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 s(t-2)/2 <= f(S, T) <= (s-1)(t²+3). 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.

The constrained Ramsey number f(G, H) also unifies certain concepts from Ramsey and anti-Ramsey theory. When H is the 4-node path P₄, f(G, H) is the usual 2-color Ramsey number R²(G). When H is the star K_{1, k+1}, f(S, T) is the local k-Ramsey number R^k_loc(G). And when G is the 3-node path P₃, f(G, H) is the anti-Ramsey number of H for proper colorings.

Date received: April 20, 2001