# Repetition thresholds for subdivided graphs and trees

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications (2012)

- Volume: 46, Issue: 1, page 123-130
- ISSN: 0988-3754

## Access Full Article

top## Abstract

top## How to cite

topOchem, Pascal, and Vaslet, Elise. "Repetition thresholds for subdivided graphs and trees." RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications 46.1 (2012): 123-130. <http://eudml.org/doc/272998>.

@article{Ochem2012,

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.},

author = {Ochem, Pascal, Vaslet, Elise},

journal = {RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications},

keywords = {combinatorics on words; repetition threshold; square-free coloring},

language = {eng},

number = {1},

pages = {123-130},

publisher = {EDP-Sciences},

title = {Repetition thresholds for subdivided graphs and trees},

url = {http://eudml.org/doc/272998},

volume = {46},

year = {2012},

}

TY - JOUR

AU - Ochem, Pascal

AU - Vaslet, Elise

TI - Repetition thresholds for subdivided graphs and trees

JO - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

PY - 2012

PB - EDP-Sciences

VL - 46

IS - 1

SP - 123

EP - 130

AB - 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.

LA - eng

KW - combinatorics on words; repetition threshold; square-free coloring

UR - http://eudml.org/doc/272998

ER -

## References

top- [1] A. Aberkane and J. Currie, There exist binary circular 5/2+ power free words of every length. Electron. J. Comb. 11 (2004) R10 Zbl1058.68084MR2035304
- [2] J. Chalopin and P. Ochem, Dejean’s conjecture and letter frequency. RAIRO-Theor. Inf. Appl. 42 (2008) 477–480. Zbl1147.68612MR2434030
- [3] F. Dejean, Sur un théorème de Thue. J. Combin. Theory. Ser. A13 (1972) 90–99. Zbl0245.20052MR300959
- [4] J. Grytczuk, Nonrepetitive colorings of graphs – a survey. Int. J. Math. Math. Sci. (2007), doi:10.1155/2007/74639 Zbl1139.05020MR2272338
- [5] P. Ochem, A generator of morphisms for infinite words. RAIRO-Theor. Inf. Appl. 40 (2006) 427–441. Zbl1110.68122MR2269202
- [6] A. Pezarski and M. Zmarz, Non-repetitive 3-Coloring of subdivided graphs. Electron. J. Comb. 16 (2009) N15 Zbl1165.05325MR2515755

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.