Anagram-Free Colourings of Graphs
Anagram-Free Colourings of Graphs
复制标题
图形的无字谜着色
DOI：
--
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
B. Sudakov
中科院分区：
文献类型：
--
作者：
Nina Kamcev;T. Luczak;B. Sudakov
如果序列 S 不包含连续符号 r1r2，则称为无字谜序列。 。 .rkrk+1。 。 .r2k 使得 rk+1。 。 .r2k 是块 r1r2 的排列。 。 .rk。在回答 Erdős 和 Brown 的问题时，Keränen 在四个符号上构造了一个无限的无字谜序列。受 Alon、Grytczuk、Hałuszczak 和 Riordan [2] 工作的启发，我们考虑了图形着色的无字谜序列的自然推广。如果给定图 G 中任何路径上的颜色序列都是无字谜的，则给定图 G 的顶点着色称为无字谜。我们将这种着色所需的最小颜色数称为 G 的字谜色数。在本文中，我们研究了几类图（如树、无次图和有界度图）的字谜色数。令人惊讶的是，我们表明存在有界度图（例如随机正则图），其中无法避免字谜，除非我们本质上为每个顶点赋予单独的颜色。
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.