Download PDF - Rainbow numbers for small stars with one edge addedAll rights reserved. Copyright exceptions and limitations apply

ArticleOriginal scientific text

Title

Rainbow numbers for small stars with one edge added

Authors 1, 1

Affiliations

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

Abstract

A subgraph of an edge-colored graph is rainbow if all of its edges have different colors. For a graph H and a positive integer n, the anti-Ramsey number f(n,H) is the maximum number of colors in an edge-coloring of Kₙ with no rainbow copy of H. The rainbow number rb(n,H) is the minimum number of colors such that any edge-coloring of Kₙ with rb(n,H) number of colors contains a rainbow copy of H. Certainly rb(n,H) = f(n,H) + 1. Anti-Ramsey numbers were introduced by Erdös et al. [5] and studied in numerous papers. We show that rb(n,K1,4+e)=n+2 in all nontrivial cases.

Keywords

ENG
rainbow number, anti-Ramsey number

Bibliography

  1. N. Alon, On the conjecture of Erdös, Simonovits and Sós concerning anti-Ramsey theorems, J. Graph Theory 7 (1983) 91-94, doi: 10.1002/jgt.3190070112.
  2. M. Axenovich and T. Jiang, Anti-Ramsey numbers for small complete bipartite graphs, Ars Combinatoria 73 (2004) 311-318.
  3. R. Diestel, Graph theory (Springer-Verlag, New York, 1997).
  4. P. Erdös and M. Simonovits, A limit theorem in graph theory, Studia Sci. Math. Hungar. 1 (1966) 51-57.
  5. P. Erdös, A. Simonovits and V. Sós, Anti-Ramsey theorems, in: Infinite and Finite Sets (A. Hajnal, R. Rado, and V. Sós, eds.), Colloq. Math. Soc. J. Bolyai (North-Holland, 1975) 633-643.
  6. I. Gorgol, On rainbow numbers for cycles with pendant edges, Graphs and Combinatorics 24 (2008) 327-331, doi: 10.1007/s00373-008-0786-8.
  7. T. Jiang, Anti-Ramsey numbers for subdivided graphs, J. Combin. Theory (B) 85 (2002) 361-366, doi: 10.1006/jctb.2001.2105.
  8. T. Jiang, Edge-colorings with no large polychromatic stars, Graphs and Combinatorics 18 (2002) 303-308, doi: 10.1007/s003730200022.
  9. T. Jiang and 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, doi: 10.1017/S096354830300590X.
  10. T. Jiang and D.B. West, Edge-colorings of complete graphs that avoid polychromatic trees, Discrete Math. 274 (2004) 137-145, doi: 10.1016/j.disc.2003.09.002.
  11. J.J. Montellano-Ballesteros, Totally multicolored diamonds, Electronic Notes in Discrete Math. 30 (2008) 231-236, doi: 10.1016/j.endm.2008.01.040.
  12. J.J. Montellano-Ballesteros and V. Neuman-Lara, An anti-Ramsey theorem on cycles, Graphs and Combinatorics 21 (2005) 343-354, doi: 10.1007/s00373-005-0619-y.
  13. I. Schiermeyer, Rainbow 5- and 6-cycles: a proof of the conjecture of Erdös, Simonovits and Sós, preprint (TU Bergakademie Freiberg, 2001).
  14. I. Schiermeyer, Rainbow numbers for matchings and complete graphs, Discrete Math. 286 (2004) 157-162, doi: 10.1016/j.disc.2003.11.057.
  15. M. Simonovits and V. Sós, On restricted colorings of Kₙ, Combinatorica 4 (1984) 101-110, doi: 10.1007/BF02579162.
Discussiones Mathematicae Graph Theory
2010/30/4
Export to PBN, Opens in new tab
Pages:
555-562
Main language of publication
English
Received
2008-12-29
Accepted
2009-10-30
Published
2010

DOI: 10.7151/dmgt.1513

Exact and natural sciences