Authors: I. Peterin, J. Schreyer, E. ©krabul'áková, A. Taranenko Title: A note on the Thue chromatic number of lexicographic produts of graphs Source: Discussiones Mathematicae Graph Theory Received 17.09.2015, Revised 18.01.2017, Accepted 18.01.2017, doi: 10.7151/dmgt.2032 | |
Abstract: A sequence is called non-repetitive if none of its subsequences forms a repetition (a sequence r_{1}r_{2}?s r_{2n} such that r_{i}=r_{n+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. | |
Keywords: non-repetitive colouring, Thue chromatic number, lexicographic product of graphs | |
Links: |