Anagram-free colorings of graphs

Abstract

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ős and Brown, Keränen constructed an infinite anagram-free sequence on four symbols. Motivated by the work of Alon, Grytczuk, Hał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.