Anagram-free graph colouring (Q1753108)

Summary: An anagram is a word of the form \(WP\) where \(W\) is a non-empty word and \(P\) is a permutation of \(W\). We study anagram-free graph colouring and give bounds on the chromatic number. \textit{N. Alon} et al. [Random Struct. Algorithms 21, No. 3--4, 336--346 (2002; Zbl 1018.05032)] asked whether anagram-free chromatic number is bounded by a function of the maximum degree. We answer this question in the negative by constructing graphs with maximum degree 3 and unbounded anagram-free chromatic number. We also prove upper and lower bounds on the anagram-free chromatic number of trees in terms of their radius and pathwidth. Finally, we explore extensions to edge colouring and \(k\)-anagram-free colouring.