Abelian Square-free Graph Colouring
Tim E. Wilson, David R. Wood · arXiv (Cornell University) · 2016
An abelian square is a word of the form $WP$ where $W$ is a non-empty word and $P$ is a permutation of $W$. We study abelian square-free graph colouring and give bounds on the chromatic number. Alon et al. (2002) asked whether abelian square-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 abelian square-free chromatic number. We also prove upper and lower bounds on the abelian square-free chromatic number of trees in terms of their radius and pathwidth. Finally, we explore extensions to edge colouring and abelian $k$-power-free colouring.