Premium
Constrained Ramsey numbers for rainbow matching
Author(s) -
Lo Allan Siu Lun
Publication year - 2011
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.20517
Subject(s) - combinatorics , rainbow , monochromatic color , mathematics , edge coloring , ramsey's theorem , graph , matching (statistics) , discrete mathematics , graph power , line graph , physics , statistics , quantum mechanics , optics
The Ramsey number R k ( G ) of a graph G is the minimum number N , such that any edge coloring of K N with k colors contains a monochromatic copy of G . The constrained Ramsey number f ( G, T ) of the graphs G and T is the minimum number N , such that any edge coloring of K N with any number of colors contains a monochromatic copy of G or a rainbow copy of T . We show that these two quantities are closely related when T is a matching. Namely, for almost all graphs G , f ( G, tK 2 ) = R t − 1 ( G ) for t ≥2. © 2010 Wiley Periodicals, Inc. J Graph Theory 67:91‐95, 2011