On a Generalization of Thue Sequences

  • Jaka Kranjc
  • Borut Lužar
  • Martina Mockovčiaková
  • Roman Soták
Keywords: Thue sequence, $k$-Thue sequence, total Thue chromatic number


A sequence is Thue or nonrepetitive if it does not contain a repetition of any length. We consider a generalization of this notion. A $j$-subsequence of a sequence $S$ is a subsequence in which two consecutive terms are at indices of difference $j$ in $S$. A $k$-Thue sequence is a sequence in which every $j$-subsequence, for $1\le j \le k$, is also Thue. It was conjectured that $k+2$ symbols are enough to construct an arbitrarily long $k$-Thue sequence and shown that the conjecture holds for $k \in \{2,3,5\}$. In this paper we present a construction of $k$-Thue sequences on $2k$ symbols, which improves the previous bound of $2k + 10\sqrt{k}$. Additionaly, we define cyclic $k$-Thue sequences and present a construction of such sequences of arbitrary lengths when $k=2$ using four symbols, with three exceptions. As a corollary, we obtain tight bounds for total Thue colorings of cycles. We conclude the paper with some open problems.
Article Number