Rainbow numbers for small stars with one edge added

Izolda Gorgol; Ewa Łazuka

Discussiones Mathematicae Graph Theory (2010)

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

Abstract

top
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 r b ( n , K 1 , 4 + e ) = n + 2 in all nontrivial cases.

How to cite

top

Izolda 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. [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. [2] M. Axenovich and T. Jiang, Anti-Ramsey numbers for small complete bipartite graphs, Ars Combinatoria 73 (2004) 311-318. Zbl1072.05041
  3. [3] R. Diestel, Graph theory (Springer-Verlag, New York, 1997). 
  4. [4] P. Erdös and M. Simonovits, A limit theorem in graph theory, Studia Sci. Math. Hungar. 1 (1966) 51-57. 
  5. [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. [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. [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. [8] T. Jiang, Edge-colorings with no large polychromatic stars, Graphs and Combinatorics 18 (2002) 303-308, doi: 10.1007/s003730200022. Zbl0991.05044
  9. [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. [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. [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. [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. [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. [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. [15] M. Simonovits and V. Sós, On restricted colorings of Kₙ, Combinatorica 4 (1984) 101-110, doi: 10.1007/BF02579162. 

NotesEmbed ?

top

You must be logged in to post comments.

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

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.