کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
5777136 | 1632570 | 2017 | 7 صفحه PDF | دانلود رایگان |
A sequence S is called anagram-free if it contains no segment 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 [Alon, N., J. Grytczuk, M. HaÅuszczak and O. Riordan, Non-repetitive colorings of graphs, Random Struct. Algor. 21 (2002), 336-346], we consider a natural generalisation of anagram-free sequences for graph colorings. A coloring of the vertices of a given graph G is called anagram-free if the sequence of colors on any path in G is anagram-free. We call the minimal number of colors needed for such a coloring the anagram-chromatic number of G.We have studied 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 basically give each vertex a separate color.
Journal: Electronic Notes in Discrete Mathematics - Volume 61, August 2017, Pages 671-677