Repetition Thresholds for Subdivided Graphs and Trees

Pascal Ochem 1 Elise Vaslet 2
1 ALGCO - Algorithmes, Graphes et Combinatoire
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : 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.
Document type :
Journal articles
Liste complète des métadonnées
Contributor : Pascal Ochem <>
Submitted on : Monday, October 8, 2012 - 10:30:02 AM
Last modification on : Thursday, May 24, 2018 - 3:59:22 PM


  • HAL Id : lirmm-00739384, version 1


Pascal Ochem, Elise Vaslet. Repetition Thresholds for Subdivided Graphs and Trees. RAIRO - Theoretical Informatics and Applications (RAIRO: ITA), EDP Sciences, 2012, 46 (1), pp.123-130. ⟨lirmm-00739384⟩



Record views