Nonrepetitive colorings of graphs
Nonrepetitive colorings of graphs
复制标题
DOI：
10.1002/rsa.10057
复制
发表时间：
2002-10
影响因子：
1
通讯作者：
N. Alon;J. Grytczuk;Mariusz Haluszczak;O. Riordan
中科院分区：
文献类型：
--
作者：
N. Alon;J. Grytczuk;Mariusz Haluszczak;O. Riordan
序列A = A1A2…AN被称为非重复，例如，A序列完全相同。符号可以在本文中产生任意长的非重复序列。是不重复的。我们通过应用Lovász局部引理显示，对于某些特殊的图形c而言，Thue数量限制为具有界限的最大程度的图形，尤其是π（g）≤cδ（g）2。我们通过给出明确的颜色来获得π（g）上的线性上限。至少有两个边缘的树。
A sequence a = a1a2 … an is said to be nonrepetitive if no two adjacent blocks of a are exactly the same. For instance, the sequence 1232321 contains a repetition 2323, while 123132123213 is nonrepetitive. A theorem of Thue asserts that, using only three symbols, one can produce arbitrarily long nonrepetitive sequences. In this paper we consider a natural generalization of Thue's sequences for colorings of graphs. A coloring of the set of edges of a given graph G is nonrepetitive if the sequence of colors on any path in G is nonrepetitive. We call the minimal number of colors needed for such a coloring the Thue number of G and denote it by π(G). The main problem we consider is the relation between the numbers π(G) and Δ(G). We show, by an application of the Lovász Local Lemma, that the Thue number stays bounded for graphs with bounded maximum degree, in particular, π(G) ≤ cΔ(G)2 for some absolute constant c. For certain special classes of graphs we obtain linear upper bounds on π(G), by giving explicit colorings. For instance, the Thue number of the complete graph Kn is at most 2n − 3, and π(T) ≤ 4(Δ(T) − 1)for any tree T with at least two edges. We conclude by discussing some generalizations and proposing several problems and conjectures. © 2002 Wiley Periodicals, Inc. Random Struct. Alg., 21: 336–346, 2002