A Note on the Thue Chromatic Number of Lexicographic Products of Graphs

Abstract

A sequence is called non-repetitive if none of its subsequences forms a repetition (a sequence r1r2⋯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.

Keywords

• non-repetitive colouring
• thue chromatic number
• lexicographic product of graphs
• 05c15
• 05c76