Résumé
A vertex colouring of a graph
G
is
nonrepetitive if for any path
P
=
(
v
1
,
v
2
,
…
,
v
2
r
)
in
G
, the first half is coloured differently from the second half. The
Thue choice number of
G
is the least integer
ℓ
such that for every
ℓ
-list assignment
L
of
G
, there exists a nonrepetitive
L
-colouring of
G
. We prove that for any positive integer
ℓ
, there is a tree
T
with
π
ch
(
T
)
>
ℓ
. On the other hand, it is proved that if
G
′
is a graph of maximum degree
Δ
, and
G
is obtained from
G
′
by attaching to each vertex
v
of
G
′
a connected graph of tree-depth at most
z
rooted at
v
, then
π
ch
(
G
)
≤
c
(
Δ
,
z
)
for some constant
c
(
Δ
,
d
)
depending only on
Δ
and
z
.
► 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.