Naslov
Anagram-Free Colourings of Graphs

Autori
KAMČEV, NINA ; ŁUCZAK, TOMASZ ; SUDAKOV, BENNY

Izvornik
Combinatorics, Probability and Computing (0963-5483) 27 (2017), 4; 623-642

Vrsta, podvrsta i kategorija rada
Radovi u časopisima, članak, znanstveni

Ključne riječi
random graphs

Sažetak
A sequence S is called anagram-free if it contains no consecutive symbols r(1)r(2)... r(k)r(k+1)... r(2k) such that r(k+1)... r(2k) is a permutation of the block r(1)r(2)...r(k). Answering a question of Erdos and Brown, Keranen constructed an infinite anagram-free sequence on four symbols. Motivated by the work of Alon, Grytczuk, Haluszczak 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.

Izvorni jezik
Engleski

Znanstvena područja
Matematika

POVEZANOST RADA