Nonrepetitive list colourings of paths
Jarosław Grytczuk , Jakub Przybyło , Xuding Zhu
AbstractA vertex colouring c of a graph G is called nonrepetitive if for every integer r ≥ 1 and every path P = (v1,v2,…,v2r) in G, the first half of P is coloured differently from the second half of P, that is, c(vj)≠c(vr+j) for some j = 1,2,…,r. This notion was inspired by a striking result of Thue asserting that the path Pn 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 πch(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 πch(Pn) ≤ 4 for every n. © 2010 Wiley Periodicals, Inc. Random Struct. Alg., 2011
|Journal series||Random Structures \& Algorithms, ISSN 1098-2418, (0 pkt)|
|Keywords in English||list coloring, local lemma, Thue sequences|
|Publication indicators||= 21; = 17|
|Citation count*||20 (2015-03-13)|
* presented citation count is obtained through Internet information analysis and it is close to the number calculated by the Publish or Perish system.