Opuscula Math. 37, no. 4 (2017), 567-575
http://dx.doi.org/10.7494/OpMath.2017.37.4.567

Opuscula Mathematica

# Anti-Ramsey numbers for disjoint copies of graphs

Izolda Gorgol
Agnieszka Görlich

Abstract. A subgraph of an edge-colored graph is called rainbow if all of its edges have different colors. For a graph $$G$$ and a positive integer $$n$$, the anti-Ramsey number $$ar(n,G)$$ is the maximum number of colors in an edge-coloring of $$K_n$$ with no rainbow copy of $$H$$. Anti-Ramsey numbers were introduced by Erdȍs, Simonovits and Sós and studied in numerous papers. Let $$G$$ be a graph with anti-Ramsey number $$ar(n,G)$$. In this paper we show the lower bound for $$ar(n,pG)$$, where $$pG$$ denotes $$p$$ vertex-disjoint copies of $$G$$. Moreover, we prove that in some special cases this bound is sharp.

Keywords: anti-Ramsey number, rainbow number, disjoint copies.

Mathematics Subject Classification: 05C55, 05C15.

Full text (pdf)

1. N. Alon, On the conjecture of Erdős, Simonovits and Sós concerning anti-Ramsey theorems, J. Graph Theory 7 (1983), 91-94.
2. A. Bialostocki, S. Gilboa, Y. Roditty, Anti-Ramsey numbers of small graphs, Ars Combin. 123, 41-53.
3. P. Erdős, M. Simonovits, A limit theorem in graph theory, Studia Sci. Math. Hungar. 1 (1966), 51-57.
4. P. Erdős, M. Simonovits, V. Sós, Anti-Ramsey theorems, [in:] A. Hajnal, R. Rado, V. Sós (eds), Infinite and finite sets, Colloq. Math. Soc. J. Bolyai, North-Holland, 1973, 633-643.
5. S. Fujita, A. Kaneko, I. Schiermeyer, K. Suzuki, A rainbow $$k$$-matching in the complete graph with $$r$$ colors, Electron. J. Combin. 16 (2009), 51.
6. S. Fujita, C. Magnant, K. Ozeki, Rainbow generalizations of Ramsey theory: A survey, Graphs Combin. 26 (2010), 1-30.
7. S. Gilboa, Y. Roditty, Anti-Ramsey numbers of graphs with small connected components, Graphs Combin. 32 (2016), 649-662.
8. I. Gorgol, On rainbow numbers for cycles with pendant edges, Graphs Combin. 24 (2008), 327-331.
9. R. Haas, M. Young, The anti-Ramsey number of perfect matching, Discrete Math. 312 (2012), 933-937.
10. T. Jiang, Edge-colorings with no large polychromatic stars, Graphs Combin. 18 (2002), 303-308.
11. T. Jiang, D.B. West, On the Erdős-Simonovits-Sós conjecture about the anti-Ramsey number of a cycle, Combin. Probab. Comput. 12 (2003), 585-598.
12. T. Jiang, D.B. West, Edge-colorings of complete graphs that avoid polychromatic trees, Discrete Math. 274 (2004), 137-145.
13. J.J. Montellano-Ballesteros, V. Neuman-Lara, An anti-Ramsey theorem on cycles, Graphs and Combinatorics 21 (2005), 343-354.
14. J.J. Montellano-Ballesteros, On totally multicolored stars, J. Graph Theory 51 (2006), 225-243.
15. J.J. Montellano-Ballesteros, Totally multicolored diamonds, Electron. Notes Discrete Math. 30 (2008), 231-236.
16. O. Ore, Arc coverings of graphs, Ann. Math. Pure Appl. 55 (1961), 315-321.
17. I. Schiermeyer, Rainbow numbers for matchings and complete graphs, Discrete Math. 286 (2004), 157-162.
18. I. Schiermeyer, R. Soták, Rainbow numbers for graphs containing small cycles, Graphs Combin. 31 (2015) 1985-1991.
• Izolda Gorgol
• Lublin University of Technology, Department of Applied Mathematics, Nadbystrzycka 38D, 20-618 Lublin, Poland
• Agnieszka Görlich
• AGH University of Science and Technology, Faculty of Applied Mathematics, al. A. Mickiewicza 30, 30-059 Krakow, Poland
• Communicated by Ingo Schiermeyer.
• Revised: 2016-07-20.
• Accepted: 2016-08-06.
• Published online: 2017-04-28.