# Rainbow numbers for small stars with one edge added

Discussiones Mathematicae Graph Theory (2010)

- Volume: 30, Issue: 4, page 555-562
- ISSN: 2083-5892

## Access Full Article

top## Abstract

top## How to cite

topIzolda Gorgol, and Ewa Łazuka. "Rainbow numbers for small stars with one edge added." Discussiones Mathematicae Graph Theory 30.4 (2010): 555-562. <http://eudml.org/doc/270898>.

@article{IzoldaGorgol2010,

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,K_\{1,4\} + e) = n + 2$ in all nontrivial cases.},

author = {Izolda Gorgol, Ewa Łazuka},

journal = {Discussiones Mathematicae Graph Theory},

keywords = {rainbow number; anti-Ramsey number},

language = {eng},

number = {4},

pages = {555-562},

title = {Rainbow numbers for small stars with one edge added},

url = {http://eudml.org/doc/270898},

volume = {30},

year = {2010},

}

TY - JOUR

AU - Izolda Gorgol

AU - Ewa Łazuka

TI - Rainbow numbers for small stars with one edge added

JO - Discussiones Mathematicae Graph Theory

PY - 2010

VL - 30

IS - 4

SP - 555

EP - 562

AB - 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,K_{1,4} + e) = n + 2$ in all nontrivial cases.

LA - eng

KW - rainbow number; anti-Ramsey number

UR - http://eudml.org/doc/270898

ER -

## References

top- [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. Zbl0456.05038
- [2] M. Axenovich and T. Jiang, Anti-Ramsey numbers for small complete bipartite graphs, Ars Combinatoria 73 (2004) 311-318. Zbl1072.05041
- [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. Zbl1180.05070
- [7] T. Jiang, Anti-Ramsey numbers for subdivided graphs, J. Combin. Theory (B) 85 (2002) 361-366, doi: 10.1006/jctb.2001.2105. Zbl1019.05047
- [8] T. Jiang, Edge-colorings with no large polychromatic stars, Graphs and Combinatorics 18 (2002) 303-308, doi: 10.1007/s003730200022. Zbl0991.05044
- [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. Zbl1063.05100
- [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. Zbl1032.05089
- [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. Zbl05285004
- [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. Zbl1075.05058
- [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. Zbl1053.05053
- [15] M. Simonovits and V. Sós, On restricted colorings of Kₙ, Combinatorica 4 (1984) 101-110, doi: 10.1007/BF02579162.

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.