Rainbow Turán Problems
Abstract
For a fixed graph H, we define the rainbow Turán number ex^*(n,H) to be the maximum number of edges in a graph on n vertices that has a proper edge-colouring with no rainbow H. Recall that the (ordinary) Turán number ex(n,H) is the maximum number of edges in a graph on n vertices that does not contain a copy of H. For any non-bipartite H we show that ex^*(n,H)=(1+o(1))ex(n,H), and if H is colour-critical we show that ex^{*}(n,H)=ex(n,H). When H is the complete bipartite graph K_{s,t} with s ≤ t we show ex^*(n,K_{s,t}) = O(n^{2-1/s}), which matches the known bounds for ex(n,K_{s,t}) up to a constant. We also study the rainbow Turán problem for even cycles, and in particular prove the bound ex^*(n,C_6) = O(n^{4/3}), which is of the correct order of magnitude.
Additional Information
Copyright © 2006 Cambridge University Press. Reprinted with permission. Received 7 June 2004; revised 7 October 2005. [Published online 4 September 2006] We thank an anonymous referee for suggestions that improved the presentation of this paper, and for drawing certain references to our attention, including the construction of Maamoun and Meyniel used in Section 2. [D.M.] Research supported in part by NSF grant DMS-0400812, and by an Alfred P. Sloan fellowship. [B.S.] Research supported in part by NSF grant DMS-0355497, a USA–Israeli BSF grant, and by an Alfred P. Sloan fellowship.Files
Name | Size | Download all |
---|---|---|
md5:55d4e7ed7d031fdfac15834700eeb61c
|
194.6 kB | Preview Download |
Additional details
- Eprint ID
- 7555
- Resolver ID
- CaltechAUTHORS:KEEcpc07
- Created
-
2007-03-03Created from EPrint's datestamp field
- Updated
-
2021-11-08Created from EPrint's last_modified field