20.500.12556/DKUM-51587 Nonrepetitive colorings of trees Neponavljajoča barvanja dreves Barvanje vozlišč grafa ▫$G$▫ je neponavljajoče, če nobena pot v ▫$G$▫ ne tvori zaporedja sestavljenega iz dveh identičnih blokov. Najmanjše število barv, ki jih potrebujemo za tako barvanje, je Thuejevo kromatično število, označimo ga s ▫$pi(G)$▫. Slavni Thuejev izrek trdi, da je ▫$pi(P) = 3$▫ za vsako pot ▫$P$▫ z vsaj štirimi vozlišči. V članku študiramo Thuejevo kromatično število na drevesih. Glede na to,da je v tem razredu ▫$pi(T)$▫ omejeno s 4, je naš namen opisati 4-kromatična drevesa. V posebnem obravnavamo 4-kritična drevesa, ki so minimalna glede na to lastnost. Čeprav obstaja mnogo dreves ▫$T$▫ s ▫$pi(T) = 4$▫, pokažemo, da ima vsako od njih primerno veliko subdivizijo ▫$H$▫, tako da je ▫$pi(H)=3$▫. Dokaz se opira na Thuejeva zaporedja z dodatnimi lastnostmi, ki vključujejo palindromske besede. Obravnavamo tudi neponavljajoča barvanja povezav na drevesih. S podobnimi argumenti dokažemo, da ima vsako drevo subdivizijo, ki jo lahko po povezavah pobarvamo z največ ▫$Delta +1$▫ barvami brez ponavljanja na poteh. 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 ▫$pi(G)$▫. A famous theorem of Thue asserts that ▫$pi(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 ▫$pi(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 ▫$pi(T)=4$▫ we show that any of them has a sufficiently large subdivision ▫$H$▫ such that ▫$pi(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 ▫$Delta + 1▫$ colors without repetitions on paths. kombinatorika na besedah neponavljajoče zaporedje Thuejevo kromatično število drevo palindrom combinatorics on words nonrepetitive sequence Thue chromatic number tree palindrome true false false Angleški jezik Neznan jezik Delo ni kategorizirano 2015-07-10 14:56:50 2015-07-10 14:56:51 2022-05-30 03:06:30 2019-07-11 07:22:57 2007 0 0 str. 163-172 iss. 2 Vol. 307 2007 0000-00-00 NiDoloceno NiDoloceno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 519.17:004 1118479 14231385 0012-365X URN:SI:UM:DK:XRSLZS8C http://dx.doi.org/10.1016/j.disc.2006.06.017 1 https://dk.um.si/Dokument.php?lang=slv&id=76147 Fakulteta za elektrotehniko, računalništvo in informatiko 0 0 0