  A sequence $S$ is called anagram-free if it contains no consecutive symbols
$r_1 r_2\dots r_k r_{k+1} \dots r_{2k}$ such that $r_{k+1} \dots r_{2k}$ is a
permutation of the block $r_1 r_2\dots r_k$. Answering a question of Erd\H{o}s
and Brown, Ker\"anen constructed an infinite anagram-free sequence on four
symbols.
  Motivated by the work of Alon, Grytczuk, Ha\l uszczak and Riordan, we
consider a natural generalisation of anagram-free sequences for graph
colorings. A coloring of the vertices of a given graph $G$ is called
anagram-free if the sequence of colors on any path in $G$ is anagram-free. We
call the minimal number of colors needed for such a coloring the
anagram-chromatic number of $G$.
  In this paper we study the anagram-chromatic number of several classes of
graphs like trees, minor-free graphs and bounded-degree graphs. Surprisingly,
we show that there are bounded-degree graphs (such as random regular graphs) in
which anagrams cannot be avoided unless we basically give each vertex a
separate color.
