A note on the Thue chromatic number of lexicographic products of graphs

preprint2014arXivOpen access

Abstract

A sequence is called non-repetitive if no of its subsequences forms a repetition (a sequence r1,r2,…,r2nr_1,r_2,\dots,r_{2n} such that ri=rn+ir_i=r_{n+i} for all 1≤i≤n1\leq i \leq n). Let GG be a graph whose vertices are coloured. A colouring φφ of the graph GG is non-repetitive if the sequence of colours on every path in GG is non-repetitive. The Thue chromatic number, denoted by π(G)π(G), is the minimum number of colours of a non-repetitive colouring of GG. In this short note we present a general upper bound for the Thue chromatic number for the lexicographic product G∘HG\circ H of graphs GG and HH with respect to some properties of the factors. This upper bound is then used to derive the exact values for π(G∘H)π(G\circ H) when GG is a complete multipartite graph and HH is an arbitrary graph.

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.