2014/09/17 by Iztok Peterin, Peterin, Iztok, Jens Schreyer +5
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory #math.CO #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.1409.5154
arxiv created 2014/09/17 · openalex publication_date 2014/09/17 · arxiv updated 2014/09/19 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A sequence is called non-repetitive if no of its subsequences forms a repetition (a sequence r1,r2,…,r2n such that ri=rn+i for all 1≤ i ≤ n). Let G be a graph whose vertices are coloured. A colouring φ of the graph G is non-repetitive if the sequence of colours on every path in G is non-repetitive. The Thue chromatic number, denoted by π(G), is the minimum number of colours of a non-repetitive colouring of G. In this short note we present a general upper bound for the Thue chromatic number for the lexicographic product G∘ H of graphs G and H with respect to some properties of the factors. This upper bound is then used to derive the exact values for π(G∘ H) when G is a complete multipartite graph and H is an arbitrary graph.