On a generalization of Thue sequences

Jaka Kranjc ; Borut Lužar ; Martina Mockovčiaková ; Roman Soták

The electronic journal of combinatorics, Tome 22 (2015) no. 2

Résumé

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.

Détail

DOI : 10.37236/4817

Classification : 68R15, 05C15
Mots-clés : Thue sequence, \(k\)-Thue sequence, total Thue chromatic number