The repetition threshold introduced by Dejean and Brandenburg is the smallest real number α such that there exists an infinite word over a k-letter alphabet that avoids β-powers for all β > α. We extend this notion to colored graphs and obtain the value of the repetition thresholds of trees and “large enough” subdivisions of graphs for every alphabet size.
@article{ITA_2012__46_1_123_0,
author = {Ochem, Pascal and Vaslet, Elise},
title = {Repetition thresholds for subdivided graphs and trees},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
volume = {46},
year = {2012},
pages = {123-130},
doi = {10.1051/ita/2011122},
mrnumber = {2904965},
zbl = {1247.68211},
language = {en},
url = {http://dml.mathdoc.fr/item/ITA_2012__46_1_123_0}
}
Ochem, Pascal; Vaslet, Elise. Repetition thresholds for subdivided graphs and trees. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 46 (2012) pp. 123-130. doi : 10.1051/ita/2011122. http://gdmltest.u-ga.fr/item/ITA_2012__46_1_123_0/
[1] and , There exist binary circular 5/2+ power free words of every length. Electron. J. Comb. 11 (2004) R10 | MR 2035304 | Zbl 1058.68084
[2] and , Dejean's conjecture and letter frequency. RAIRO-Theor. Inf. Appl. 42 (2008) 477-480. | Numdam | MR 2434030 | Zbl 1147.68612
[3] , Sur un théorème de Thue. J. Combin. Theory. Ser. A 13 (1972) 90-99. | MR 300959 | Zbl 0245.20052
[4] , Nonrepetitive colorings of graphs - a survey. Int. J. Math. Math. Sci. (2007), doi:10.1155/2007/74639 | MR 2272338 | Zbl 1139.05020
[5] , A generator of morphisms for infinite words. RAIRO-Theor. Inf. Appl. 40 (2006) 427-441. | Numdam | MR 2269202 | Zbl 1110.68122
[6] and , Non-repetitive 3-Coloring of subdivided graphs. Electron. J. Comb. 16 (2009) N15 | MR 2515755 | Zbl 1165.05325