Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published January 1, 2007 | public
Journal Article Open

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

KEEcpc07.pdf
Files (194.6 kB)
Name Size Download all
md5:55d4e7ed7d031fdfac15834700eeb61c
194.6 kB Preview Download

Additional details

Created:
August 22, 2023
Modified:
October 16, 2023