Anagram-Free Colourings of Graphs

Nina Kamčev, Tomasz Łuczak, Benny Sudakov

Research output: Contribution to journalArticleResearchpeer-review

5 Citations (Scopus)

Abstract

A sequence S is called anagram-free if it contains no consecutive symbols r1r2⋯rkrk+1⋯r2k such that rk+1⋯r2k is a permutation of the block r1r2⋯rk. 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 [2], we consider a natural generalization of anagram-free sequences for graph colourings. A colouring of the vertices of a given graph G is called anagram-free if the sequence of colours on any path in G is anagram-free. We call the minimal number of colours needed for such a colouring 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 essentially give each vertex a separate colour.

Original languageEnglish
Pages (from-to)623-642
Number of pages20
JournalCombinatorics Probability and Computing
Volume27
Issue number4
DOIs
Publication statusPublished - 1 Jul 2018
Externally publishedYes

Cite this