Constrained Ramsey numbers for rainbow matching |
| |
Authors: | Allan Siu Lun Lo |
| |
Affiliation: | Department of pure Mathematics and Mathematical Statistics, University of Cambridge, Cambridge CB3 0WB, U.K. |
| |
Abstract: | The Ramsey number Rk(G) of a graph G is the minimum number N, such that any edge coloring of KN 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 KN 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, tK2) = Rt ? 1(G) for t≥2. © 2010 Wiley Periodicals, Inc. J Graph Theory 67:91‐95, 2011 |
| |
Keywords: | Ramsey constrained Ramsey rainbow matching |
|
|