Premium
Constrained Ramsey numbers of graphs
Author(s) -
Jamison Robert E.,
Jiang Tao,
Ling Alan C. H.
Publication year - 2003
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.10072
Subject(s) - combinatorics , mathematics , star (game theory) , integer (computer science) , graph , discrete mathematics , computer science , mathematical analysis , programming language
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 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