Nonrepetitive List Colourings of Paths
A vertex colouring c of a graph G is called nonrepetitive if for every integer r >= 1 and every path P = (v(1), v(2),..., v(2r)) in G, the first half of P is coloured differently from the second half of P, that is, c(v(j)) not equal c(v(r+ j)) for some j = 1, 2,..., r. This notion was inspired by a striking result of Thue asserting that the path P(n) on n vertices has a nonrepetitive three-colouring, no matter how large n is. A k-list assignment of a graph G is a mapping L which assigns a set L(v) of k permissible colours to each vertex v of G. The Thue choice number of G, denoted by pi(eh) (G), is the least integer k such that for every k-list assignment L there is a nonrepetitive colouring c of G satisfying c(v). L(v) for every vertex v of G. Using the Lefthanded Local Lemma we prove that pi(eh) (P(n)) <= 4 for every n. (C) 2010 Wiley Periodicals, Inc. Random Struct. Alg., 38, 162-173, 2011
local lemma thue sequences list coloring