On a generalization of Thue sequences

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

\(k\)-Thue sequence Thue sequence total Thue chromatic number

Coloring of graphs and hypergraphs (05C15) Combinatorics on words (68R15)

Summary: A sequence is \textit{Thue} or \textit{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\)-\textit{Thue sequence} is a sequence in which every \(j\)-subsequence, for \(1\leq j \leq 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.

Recommendations

Cites work

Cited in

(14)

This page was built for publication: On a generalization of Thue sequences

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