Hostname: page-component-7b7567c8c-mnklg Total loading time: 0 Render date: 2026-11-12T10:41:52.790Z Has data issue: false hasContentIssue false
  • English
  • Français

Repetition thresholds for subdivided graphs and trees

Published online by Cambridge University Press:  07 October 2011

Pascal Ochem and
Elise Vaslet
Pascal Ochem
Affiliation:
CNRS, LRI, Université Paris-Sud 11, 91405 Orsay Cedex, France. ochem@lri.fr
Elise Vaslet
Affiliation:
IML, UMR 6206, Université Aix-Marseille II, Campus de Luminy, Case 907, 13288 Marseille Cedex 9, France; vaslet@iml.univ-mrs.fr

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

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.

Keywords

Combinatorics on wordsrepetition thresholdsquare-free coloring

References

Références

Aberkane, A. and Currie, J., There exist binary circular 5/2+ power free words of every length. Electron. J. Comb. 11 (2004) R10 Google Scholar
Chalopin, J. and Ochem, P., Dejean’s conjecture and letter frequency. RAIRO-Theor. Inf. Appl. 42 (2008) 477–480. Google Scholar
Dejean, F., Sur un théorème de Thue. J. Combin. Theory. Ser. A 13 (1972) 90–99. Google Scholar
J. Grytczuk, Nonrepetitive colorings of graphs – a survey. Int. J. Math. Math. Sci. (2007), doi:10.1155/2007/74639
Ochem, P., A generator of morphisms for infinite words. RAIRO-Theor. Inf. Appl. 40 (2006) 427–441. Google Scholar
Pezarski, A. and Zmarz, M., Non-repetitive 3-Coloring of subdivided graphs. Electron. J. Comb. 16 (2009) N15 Google Scholar