Constrained Ramsey numbers of graphs

Authors:
Publisher website
Google Scholar
Abstract
Given two graphs G and H, let f(G,H) denote the minimum integer n such that in every coloring of the edges of Kn, 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)(t2+3t). 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

This publication has 16 references indexed in Scilit: