# 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

### Abstract

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.
Published
2015-05-22
Article Number
P2.33
{"ft_lang_label":"__label__en","ft_lang_prob":0.9072263,"math_prob":0.9932407,"size":1101,"snap":"2023-40-2023-50","text_gpt3_token_len":299,"char_repetition_ratio":0.16408387,"word_repetition_ratio":0.0,"special_character_ratio":0.24523161,"punctuation_ratio":0.0990566,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.99836737,"pos_list":[0],"im_url_duplicate_count":[null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2023-12-01T06:45:34Z\",\"WARC-Record-ID\":\"<urn:uuid:b3cb1a48-1ff6-4dcc-96be-28b8e1e7bcf5>\",\"Content-Length\":\"15799\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:2767e958-304d-40b7-b3fd-63f112d980ee>\",\"WARC-Concurrent-To\":\"<urn:uuid:76352cfc-0549-4e7b-8260-02eb9899bcb0>\",\"WARC-IP-Address\":\"150.203.186.177\",\"WARC-Target-URI\":\"https://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i2p33\",\"WARC-Payload-Digest\":\"sha1:GU7JASNA6FLWLQ3WTB5MEU44EXKTUTZS\",\"WARC-Block-Digest\":\"sha1:W3CS44ETWHJDU3PQY7JMTYTA6Y6U4YM5\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2023/CC-MAIN-2023-50/CC-MAIN-2023-50_segments_1700679100276.12_warc_CC-MAIN-20231201053039-20231201083039-00040.warc.gz\"}"}