Anti-Ramsey numbers for disjoint copies of graphs

• Autorzy: Gorgol I. , Gorlich A.

Identyfikatory

DOI

10.7494/OpMath.2017.37.4.567

• Języki publikacji: EN

Abstrakty

PL

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 Kn with no rainbow copy of H. Anti-Ramsey numbers were introduced by Erdos, 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.

Słowa kluczowe

EN

anti-Ramsey number; rainbow number; disjoint copies

• Wydawca: AGH University of Science and Technology Press
• Czasopismo: Opuscula Mathematica
• Rocznik: 2017
• Tom: Vol. 37, no. 4
• Strony: 567--575
• Opis fizyczny: Bibliogr. 18 poz.

Twórcy

autor

Gorgol I.

• Lublin University of Technology Department of Applied Mathematics Nadbystrzycka 38D, 20-618 Lublin, Poland

autor

Gorlich A.

• AGH University of Science and Technology Faculty of Applied Mathematics al. A. Mickiewicza 30, 30-059 Krakow, Poland

Bibliografia

• [1] N. Alon, On the conjecture of Erdos, Simonovits and Sós concerning anti-Ramsey theorems, J. Graph Theory 7 (1983), 91-94.
• [2] A. Białostocki, 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. Erdos, 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 Erdos-Simonovits-Sos 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-bara, 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. Sotak, Rainbow numbers for graphs containing small cycles, Graphs Combin. 31 (2015) 1985-1991.

Uwagi

PL

Opracowanie ze środków MNiSW w ramach umowy 812/P-DUN/2016 na działalność upowszechniającą naukę (zadania 2017).