Hostname: page-component-74656f9884-j7cmm Total loading time: 0 Render date: 2026-11-09T01:03:39.719Z 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: pw236@cam.ac.uk)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

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$.

Information

Type
Paper
Copyright
2006 Cambridge University Press