| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 418543 | Discrete Applied Mathematics | 2011 | 5 Pages |
A vertex colouring of a graph GG is nonrepetitive if for any path P=(v1,v2,…,v2r)P=(v1,v2,…,v2r) in GG, the first half is coloured differently from the second half. The Thue choice number of GG is the least integer ℓℓ such that for every ℓℓ-list assignment LL of GG, there exists a nonrepetitive LL-colouring of GG. We prove that for any positive integer ℓℓ, there is a tree TT with πch(T)>ℓ. On the other hand, it is proved that if G′G′ is a graph of maximum degree ΔΔ, and GG is obtained from G′G′ by attaching to each vertex vv of G′G′ a connected graph of tree-depth at most zz rooted at vv, then πch(G)≤c(Δ,z) for some constant c(Δ,d)c(Δ,d) depending only on ΔΔ and zz.
► We prove that the Thue choice number of trees is unbounded. ► The class of graphs with bounded maximum degree has bounded Thue choice number. ► The class of graphs with bounded tree-depth has bounded Thue choice number. ► A larger class (containing both classes above) of graphs has bounded Thue choice number.
