Hostname: page-component-cd9895bd7-fscjk Total loading time: 0 Render date: 2024-12-23T13:53:24.062Z Has data issue: false hasContentIssue false

An Upper Bound for Constrained Ramsey Numbers

Published online by Cambridge University Press:  07 June 2006

PETER WAGNER
Affiliation:
Department of Pure Mathematics and Mathematical Statistics, Centre for Mathematical Sciences, University of Cambridge, Wilberforce Road, Cambridge, CB3 0WB, UK (e-mail: [email protected])

Abstract

Let $s$ and $t$ be integers satisfying $s \geq 2$ and $t \geq 2$. Let $S$ be a tree of size $s$, and let $P_t$ be the path of length $t$. We show in this paper that, for every edge-colouring of the complete graph on $n$ vertices, where $n=224(s-1)^2t$, there is either a monochromatic copy of $S$ or a rainbow copy of $P_t$. So, in particular, the number of vertices needed grows only linearly in $t$.

Type
Paper
Copyright
2006 Cambridge University Press

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)