Repetition thresholds for subdivided graphs and trees

DOI10.1051/ITA/2011122MaRDI QIDQ2911431zbMATH OpenOpenAlexFDO

Authors Pascal Ochem, Elise Vaslet

Publication date 31 August 2012

Published in RAIRO. Theoretical Informatics and Applications (Search for Journal in Brave)

Full work available at URL https://eudml.org/doc/222007, https://semanticscholar.org/paper/3182c345075826e4b8516903ee7d95a6b1fd1511

zbMATH Keywords

combinatorics on wordsrepetition thresholdsquare-free coloring

Mathematics Subject Classification ID

Trees (05C05) Coloring of graphs and hypergraphs (05C15) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Combinatorics on words (68R15)

Recommendations

• On repetition thresholds of caterpillars and trees of bounded degree
• Subdivision thresholds for two classes of graphs
• On the number of subtrees for almost all graphs
• Repetitions in graphs and sequences
• On subgraph number independence in trees
• Uniqueness thresholds on trees versus graphs
• Repetition of spectral radiuses among connected induced subgraphs
• Insertion-tolerance and repetitiveness of random graphs
• On the domination subdivision numbers of trees

Cites work

• A generator of morphisms for infinite words
• Dejean's conjecture and letter frequency
• Non-repetitive 3-coloring of subdivided graphs
• Nonrepetitive colorings of graphs -- a survey
• Sur un théorème de Thue
• There exist binary circular 5/2^+ power free words of every length

Cited in

(8)

• On repetition thresholds of caterpillars and trees of bounded degree
• Fractional meanings of nonrepetitiveness
• Circular repetition thresholds on some small alphabets: last cases of Gorbunova's conjecture
• Nonrepetitively 3-colorable subdivisions of graphs with a logarithmic number of subdivisions per edge
• Finite repetition threshold for large alphabets
• Repetitions in graphs and sequences
• The weak circular repetition threshold over large alphabets
• An upper bound on asymptotic repetition threshold of balanced sequences via colouring of the Fibonacci sequence

This page was built for publication: Repetition thresholds for subdivided graphs and trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2911431)