Proceedings of the American Mathematical Society

			Journals Home Search Author Info Subscribe Tech Support My Subscriptions Help
ISSN 1088-6826(e) ISSN 0002-9939(p)

Rainbow decompositions

Author(s): Raphael Yuster
Journal: Proc. Amer. Math. Soc. 136 (2008), 771-779.
MSC (2000): Primary 05C15, 05C70, 05B40, 03E05
Posted: November 30, 2007
MathSciNet review: 2361848
Retrieve article in: PDF

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 there exists an so that for all , if

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

then every properly edge-colored

contains $\binom{n}{2}/\binom{k}{2}$ pairwise edge-disjoint rainbow copies of

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

References:

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 's into a , 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 ``http://www.msci.memphis.edu/~balistep/Abstracts.html''.
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 -factors, The Electronic Journal of Combinatorics 13 (2006), #R13. MR 2200541 (2006k:05111)

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