Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS

   
Mobile Device Pairing
Green Open Access
Proceedings of the American Mathematical Society
Proceedings of the American Mathematical Society
ISSN 1088-6826(online) ISSN 0002-9939(print)

 

Rainbow decompositions


Author: Raphael Yuster
Journal: Proc. Amer. Math. Soc. 136 (2008), 771-779
MSC (2000): Primary 05C15, 05C70, 05B40, 03E05
Published electronically: November 30, 2007
MathSciNet review: 2361848
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: A rainbow coloring of a graph is a coloring of the edges with distinct colors. We prove the following extension of Wilson's Theorem. For every integer $ k$ there exists an $ n_0=n_0(k)$ so that for all $ n > n_0$, if

$\displaystyle n \bmod k(k-1) \in \{1,k\},$

then every properly edge-colored $ K_n$ contains $ \binom{n}{2}/\binom{k}{2}$ pairwise edge-disjoint rainbow copies of $ K_k$.

Our proof uses, as a main ingredient, a double application of the probabilistic method.


References [Enhancements On Off] (What's this?)


Similar Articles

Retrieve articles in Proceedings of the American Mathematical Society with MSC (2000): 05C15, 05C70, 05B40, 03E05

Retrieve articles in all journals with MSC (2000): 05C15, 05C70, 05B40, 03E05


Additional Information

Raphael Yuster
Affiliation: Department of Mathematics, University of Haifa, Haifa 31905, Israel
Email: raphy@math.haifa.ac.il

DOI: http://dx.doi.org/10.1090/S0002-9939-07-09204-0
PII: S 0002-9939(07)09204-0
Received by editor(s): September 28, 2006
Published electronically: November 30, 2007
Communicated by: Jim Haglund
Article copyright: © Copyright 2007 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.