Geodesic
Anti-Ramsey Number of Hanoi Graphs
Discussiones Mathematicae. Graph Theory, Tome 39 (2019) no. 1, pp. 285-296.

Voir la notice de l'article provenant de la source Library of Science

Let ar(G,H) be the largest number of colors such that there exists an edge coloring of G with ar(G,H) colors such that each subgraph isomorphic to H has at least two edges in the same color. We call ar(G,H) the anti- Ramsey number for a pair of graphs (G,H). This notion was introduced by Erdős, Simonovits and Sόs in 1973 and studied in numerous papers. Hanoi graphs were introduced by Scorer, Grundy and Smith in 1944 as the model of the well known Tower of Hanoi puzzle. In the paper we study the anti-Ramsey number of Hanoi graphs and consider them both as the graph G and H. Among others we present the exact value of the anti-Ramsey number in case when both graphs are constructed for the same number of pegs.
Keywords: anti-Ramsey number, rainbow number, Hanoi graph 
@article{DMGT_2019_39_1_a21,
     author = {Gorgol, Izolda and Lechowska, Anna},
     title = {Anti-Ramsey {Number} of {Hanoi} {Graphs}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {285--296},
     publisher = {mathdoc},
     volume = {39},
     number = {1},
     year = {2019},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2019_39_1_a21/}
}
TY  - JOUR
AU  - Gorgol, Izolda
AU  - Lechowska, Anna
TI  - Anti-Ramsey Number of Hanoi Graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2019
SP  - 285
EP  - 296
VL  - 39
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2019_39_1_a21/
LA  - en
ID  - DMGT_2019_39_1_a21
ER  - 
%0 Journal Article
%A Gorgol, Izolda
%A Lechowska, Anna
%T Anti-Ramsey Number of Hanoi Graphs
%J Discussiones Mathematicae. Graph Theory
%D 2019
%P 285-296
%V 39
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2019_39_1_a21/
%G en
%F DMGT_2019_39_1_a21
Gorgol, Izolda; Lechowska, Anna. Anti-Ramsey Number of Hanoi Graphs. Discussiones Mathematicae. Graph Theory, Tome 39 (2019) no. 1, pp. 285-296. http://geodesic.mathdoc.fr/item/DMGT_2019_39_1_a21/

[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] D. Arett and S. Doree, Coloring and counting on the Tower of Hanoi graphs, Math. Mag. 83 (2010) 202-208. doi: 10.4169/002557010X494841

[3] M. Axenovich, H. Harborth, A. Kemnitz, M. Möller and I. Schiermeyer, Rainbows in the hypercube, Graphs Combin. 23 (2007) 123-133. doi: 10.1007/s00373-007-0691-6

[4] M. Axenovich and T. Jiang, Anti-Ramsey numbers for small complete bipartite graphs, Ars Combin. 73 (2004) 311-318.

[5] M. Axenovich, T. Jiang and A. K¨undgen, Bipartite anti-Ramsey numbers of cycles, J. Graph Theory 47 (2004) 9-28. doi: 10.1002/jgt.20012

[6] J.-P. Bode, D. Grimm and A. Kemnitz, Hypercube-anti-Ramsey numbers of Q5, Ars Combin. 110 (2013) 105-111.

[7] T. Bousch, La quatrieme tour de Hanoi, Bull. Belg. Math. Soc. Simon Stevin 21 (2014) 895-912.

[8] R. Diestel, Graph Theory (Springer-Verlag, New York, 1997).

[9] 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 (Ed(s)), (Colloq. Math. Soc. J. Bolyai, North- Holland, 1973) 633-643.

[10] S. Fujita, A. Kaneko, I. Schiermeyer and K. Suzuki, A Rainbow k-matching in the complete graph with r colors, Electron. J. Combin. 16 (2009) #R51.

[11] S. Fujita, C. Magnant and K. Ozeki, Rainbow generalizations of Ramsey theory: A survey, Graphs Combin. 26 (2010) 1-30. doi: 10.1007/s00373-010-0891-3

[12] I. Gorgol, Anti-Ramsey numbers in complete split graphs, Discrete Math. 339 (2016) 1944-1949. doi: 10.1016/j.disc.2015.10.038

[13] R. Haas and M. Young, The anti-Ramsey number of perfect matching, Discrete Math. 312 (2012) 933-937. doi: 10.1016/j.disc.2011.10.017

[14] A.M. Hinz and D. Parisse, Coloring Hanoi and Sierpiński graphs, Discrete Math. 312 (2012) 1521-1535. doi: 10.1016/j.disc.2011.08.019

[15] A.M. Hinz and D. Parisse, On the planarity of Hanoi graphs, Expo. Math. 20 (2002) 264-267. doi: 10.1016/S0723-0869(02)80023-8

[16] A.M. Hinz, S. Klavžar, U. Milutinović and C. Petr, The Tower of Hanoi - Myths and Maths (Birkh¨auser/Springer, Basel, 2013).

[17] M. Hornák, S. Jendrol’, I. Schiermeyer and R. Soták, Rainbow numbers for cycles in plane triangulations, J. Graph Theory 78 (2015) 248-257. doi: 10.1002/jgt.21803

[18] T. Jiang, Edge-colorings with no large polychromatic stars, Graphs Combin. 18 (2002) 303-308. doi: 10.1007/s003730200022

[19] 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

[20] 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

[21] S. Jendrol’, I. Schiermeyer and J. Tu, Rainbow numbers for matchings in plane triangulations, Discrete Math. 331 (2014) 158-164. doi: 10.1016/j.disc.2014.05.012

[22] S. Klavžar, U. Milutinović and C. Petr, Combinatorics of topmost discs of multi-peg Tower of Hanoi problem, Ars Combin. 59 (2001) 55-64.

[23] X. Li, J. Tu and Z. Jin, Bipartite rainbow numbers of matchings, Discrete Math. 309 (2009) 2575-2578. doi: 10.1016/j.disc.2008.05.011

[24] J.J. Montellano-Ballesteros and V. Neuman-Lara, An anti-Ramsey theorem on cy- cles, Graphs Combin. 21 (2005) 343-354. doi: 10.1007/s00373-005-0619-y

[25] J.J. Montellano-Ballesteros, On totally multicolored stars, J. Graph Theory 51 (2006) 225-243. doi: 10.1002/jgt.20140

[26] R.S. Scorer, P.M. Grundy and C.A.B. Smith, Some binary games, Math. Gaz. 28 (1944) 96-103. doi: 10.2307/3606393

[27] I. Schiermeyer, Rainbow numbers for matchings and complete graphs, Discrete Math. 286 (2004) 157-162. doi: 10.1016/j.disc.2003.11.057.