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. Alon et al.[Random Structures & Algorithms 2002] 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.
@article{10_37236_6267,
author = {Tim E. Wilson and David R. Wood},
title = {Anagram-free graph colouring},
journal = {The electronic journal of combinatorics},
year = {2018},
volume = {25},
number = {2},
doi = {10.37236/6267},
zbl = {1390.05077},
url = {http://geodesic.mathdoc.fr/articles/10.37236/6267/}
}
TY - JOUR
AU - Tim E. Wilson
AU - David R. Wood
TI - Anagram-free graph colouring
JO - The electronic journal of combinatorics
PY - 2018
VL - 25
IS - 2
UR - http://geodesic.mathdoc.fr/articles/10.37236/6267/
DO - 10.37236/6267
ID - 10_37236_6267
ER -
%0 Journal Article
%A Tim E. Wilson
%A David R. Wood
%T Anagram-free graph colouring
%J The electronic journal of combinatorics
%D 2018
%V 25
%N 2
%U http://geodesic.mathdoc.fr/articles/10.37236/6267/
%R 10.37236/6267
%F 10_37236_6267
Tim E. Wilson; David R. Wood. Anagram-free graph colouring. The electronic journal of combinatorics, Tome 25 (2018) no. 2. doi: 10.37236/6267
