2.
Nonrepetitive colorings of treesBoštjan Brešar,
J. Grytczuk,
Sandi Klavžar,
S. Niwczyk,
Iztok Peterin, 2007, izvirni znanstveni članek
Opis: 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.
Ključne besede: kombinatorika na besedah, neponavljajoče zaporedje, Thuejevo kromatično število, drevo, palindrom, combinatorics on words, nonrepetitive sequence, Thue chromatic number, tree, palindrome
Objavljeno: 10.07.2015; Ogledov: 588; Prenosov: 71
Povezava na celotno besedilo
