I. Peterin, J. Schreyer, E. ©krabul'áková, A. Taranenko
A note on the Thue chromatic number of lexicographic produts of graphs
Discussiones Mathematicae Graph Theory
Received 17.09.2015, Revised 18.01.2017, Accepted 18.01.2017, doi: 10.7151/dmgt.2032
A sequence is called non-repetitive if none of its subsequences forms a repetition (a sequence r1r2?s 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 two general upper bounds for the Thue chromatic number for the lexicographic product G° H of graphs G and H with respect to some properties of the factors. One upper bound is then used to derive the exact values for π(G° H) when G is a complete multipartite graph and H an arbitrary graph.
non-repetitive colouring, Thue chromatic number, lexicographic product of graphs