Nonrepetitive colorings of trees |
| |
Authors: | B Brešar |
| |
Institution: | a University of Maribor, FEECS, Smetanova 17, 2000 Maribor, Slovenia b Faculty of Mathematics, Informatics and Econometrics, University of Zielona Góra, 65-516 Zielona Góra, Poland c Department of Mathematics and Computer Science, University of Maribor, PeF, Koroška cesta 160, 2000 Maribor, Slovenia |
| |
Abstract: | 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). A famous theorem of Thue asserts that π(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) 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 we show that any of them has a sufficiently large subdivision H such that π(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 colors without repetitions on paths. |
| |
Keywords: | primary 68R15 secondary 11B83 05C05 |
本文献已被 ScienceDirect 等数据库收录! |
|