Squarefree word
From Wikipedia, the free encyclopedia
A squarefree word is a word that does not contain any subword twice in a row. There exist infinite squarefree words in any alphabet with three or more symbols, as proved by Axel Thue. To build an infinite squarefree word in the alphabet {a, b, c}, start with any word w1 from this alphabet and obtain the word wi + 1 by replacing each a in w1 with abcbacbcabcba, each b with bcacbacabcacb, and each c with cabacbabcabac (this example was shown by J. Leech). It is possible to check that the sequence converges to the infinite squarefree word abcbacbcabcbabcacbacabcacbcabacbabcabacbcacbacabcacb...
Over a two-letter alphabet {a, b} the only square-free words are the empty word and a, b, ab, ba, aba, and bab.
The Thue number of a graph G is the smallest number k such that G has a k-coloring for which the sequence of colors along every non-repeating path is squarefree.
