Anagram-free graph colouring

Tim E. Wilson, David R. Wood

Research output: Contribution to journalArticleResearchpeer-review

2 Citations (Scopus)

Abstract

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.

Original languageEnglish
Article number#P2.20
Number of pages18
JournalThe Electronic Journal of Combinatorics
Volume25
Issue number2
Publication statusPublished - 11 May 2018

Cite this