کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4651237 | 1342528 | 2007 | 10 صفحه PDF | دانلود رایگان |
A coloring of the vertices of a graph G is nonrepetitive if no path in G forms a sequence consisting of two identical blocks. The minimum number of colors needed is the Thue chromatic number , denoted by π(G)π(G). A famous theorem of Thue asserts that π(P)=3π(P)=3 for any path P with at least four vertices. In this paper we study the Thue chromatic number of trees. In view of the fact that π(T)π(T) is bounded by 4 in this class we aim to describe the 4-chromatic trees. In particular, we study the 4-critical trees which are minimal with respect to this property. Though there are many trees T with π(T)=4π(T)=4 we show that any of them has a sufficiently large subdivision H such that π(H)=3π(H)=3. The proof relies on Thue sequences with additional properties involving palindromic words . We also investigate nonrepetitive edge colorings of trees. By a similar argument we prove that any tree has a subdivision which can be edge-colored by at most Δ+1Δ+1 colors without repetitions on paths.
Journal: Discrete Mathematics - Volume 307, Issue 2, 28 January 2007, Pages 163–172