Remote Access Proceedings of the American Mathematical Society
Green Open Access

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?)

  • 1. N. Alon, T. Jiang, Z. Miller and D. Pritikin, Properly colored subgraphs and rainbow subgraphs in edge-colorings with local constraints, Random Struct. Algorithms 23 (2003), No. 4, 409-433. MR 2016871 (2004i:05106)
  • 2. B. Bollobás, Modern Graph Theory, Springer-Verlag, 1998. MR 1633290 (99h:05001)
  • 3. A.E. Brouwer, Optimal packing of $ K_4$'s into a $ K_n$, J. Combin. Theory, Ser. A 26 (1979), 278-297. MR 535158 (80j:05049)
  • 4. G. Chen, R. Schelp and B. Wei, Monochromatic - rainbow Ramsey numbers, 14th Cumberland Conference Abstracts. Posted at ``''.
  • 5. C.J. Colbourn and J.H. Dinitz, CRC Handbook of Combinatorial Design, CRC Press 1996. MR 1392993 (97a:05001)
  • 6. P. Erdős and R. Rado, A combinatorial theorem, J. London Math. Soc. 25 (1950), 249-255. MR 0037886 (12:322f)
  • 7. R. Jamison, T. Jiang and A. Ling, Constrained Ramsey numbers, J. Graph Theory 42 (2003), No. 1, 1-16. MR 1943103 (2003m:05129)
  • 8. P. Keevash, D. Mubayi, B. Sudakov and J. Verstraete, Rainbow Turán Problems, Combinatorics, Probability, and Computing 16 (2007), 109-126. MR 2286514 (2007i:05092)
  • 9. T.P. Kirkman, On a Problem in Combinatorics, Cambridge Dublin Math. J. 2 (1847), 191-204.
  • 10. R. M. Wilson, Decomposition of complete graphs into subgraphs isomorphic to a given graph, Congressus Numerantium XV (1975), 647-659. MR 0396347 (53:214)
  • 11. R. M. Wilson, An existence theory for pairwise balanced designs II. The structure of PBD-closed sets and the existence conjectures, J. Combin. Theory, Ser. A 13 (1972), 246-273. MR 0304204 (46:3339)
  • 12. R. Yuster, Rainbow $ H$-factors, The Electronic Journal of Combinatorics 13 (2006), #R13. MR 2200541 (2006k:05111)

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

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.

American Mathematical Society