Hostname: page-component-78c5997874-m6dg7 Total loading time: 0 Render date: 2024-11-03T05:44:13.809Z 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. [email protected]
Elise Vaslet
Affiliation:
IML, UMR 6206, Université Aix-Marseille II, Campus de Luminy, Case 907, 13288 Marseille Cedex 9, France; [email protected]
Get access

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.

Keywords

Combinatorics on wordsrepetition thresholdsquare-free coloring
Type
Research Article
Information
RAIRO - Theoretical Informatics and Applications , Volume 46 , Issue 1: Special issue dedicated to the 13th "Journées Montoises d'Informatique Théorique" , January 2012 , pp. 123 - 130
Copyright
© EDP Sciences 2011

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

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