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.
- N. Alon, On the conjecture of Erdős, Simonovits and Sós concerning anti-Ramsey theorems, J. Graph Theory 7 (1983), 91-94.
- A. Bialostocki, S. Gilboa, Y. Roditty, Anti-Ramsey numbers of small graphs, Ars Combin. 123, 41-53.
- P. Erdős, M. Simonovits, A limit theorem in graph theory, Studia Sci. Math. Hungar. 1 (1966), 51-57.
- 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.
- 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.
- S. Fujita, C. Magnant, K. Ozeki, Rainbow generalizations of Ramsey theory: A survey, Graphs Combin. 26 (2010), 1-30.
- S. Gilboa, Y. Roditty, Anti-Ramsey numbers of graphs with small connected components, Graphs Combin. 32 (2016), 649-662.
- I. Gorgol, On rainbow numbers for cycles with pendant edges, Graphs Combin. 24 (2008), 327-331.
- R. Haas, M. Young, The anti-Ramsey number of perfect matching, Discrete Math. 312 (2012), 933-937.
- T. Jiang, Edge-colorings with no large polychromatic stars, Graphs Combin. 18 (2002), 303-308.
- 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.
- T. Jiang, D.B. West, Edge-colorings of complete graphs that avoid polychromatic trees, Discrete Math. 274 (2004), 137-145.
- J.J. Montellano-Ballesteros, V. Neuman-Lara, An anti-Ramsey theorem on cycles, Graphs and Combinatorics 21 (2005), 343-354.
- J.J. Montellano-Ballesteros, On totally multicolored stars, J. Graph Theory 51 (2006), 225-243.
- J.J. Montellano-Ballesteros, Totally multicolored diamonds, Electron. Notes Discrete Math. 30 (2008), 231-236.
- O. Ore, Arc coverings of graphs, Ann. Math. Pure Appl. 55 (1961), 315-321.
- I. Schiermeyer, Rainbow numbers for matchings and complete graphs, Discrete Math. 286 (2004), 157-162.
- 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.
- Received: 2016-03-10.
- Revised: 2016-07-20.
- Accepted: 2016-08-06.
- Published online: 2017-04-28.
