Nonrepetitive list colourings of paths

Jarosław Grytczuk , Jakub Przybyło , Xuding Zhu

Abstract

A 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
Author Jarosław Grytczuk (FMIS / DAC)
Jarosław Grytczuk,,
- Department of Algebra and Combinatorics
, Jakub Przybyło - [AGH University of Science and Technology (AGH)]
Jakub Przybyło,,
-
- Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie
, Xuding Zhu - [Zhejiang Normal University]
Xuding Zhu,,
-
-
Journal seriesRandom Structures \& Algorithms, ISSN 1098-2418, (0 pkt)
Issue year2011
Vol38
No1-2
Pages162–173
Keywords in Englishlist coloring, local lemma, Thue sequences
DOIDOI:10.1002/rsa.20347
URL http://onlinelibrary.wiley.com/doi/10.1002/rsa.20347/abstract
Score (nominal)0
Score sourcejournalList
Publication indicators Scopus Citations = 21; WoS Citations = 17
Citation count*20 (2015-03-13)
Cite
Share Share

Get link to the record


* presented citation count is obtained through Internet information analysis and it is close to the number calculated by the Publish or Perish system.
Back
Confirmation
Are you sure?