F-WORM colorings of some 2-trees: partition vectors

angleški

2019

letnik 16, številka 1

2-drevo   maksimalen zunanjeravninski   razdelitev   Stirlingova števila

Univerza na Primorskem, Fakulteta za naravoslovje, matematiko in informacijske tehnologije
(Obvezni izvod spletne publikacije)

Naj bo ?$\mathscr{F} = \{F_1, \ldots, F_t\}$? zbirka različnih podgrafov grafa ?$G = (V, E)$?. ?$\mathscr{F}$?-WORM barvanje grafa ?$G$? je takšno barvanje njegovih vozlišč, pri katerem nobena kopija nobenega od podgrafov ?$F_i \in \mathscr{F}$? ni ne enobarvna ne mavrična. To je posplošitev pojma ?$F$?-WORM barvanja, ki so ga nedavno vpeljali W. Goddard, K. Wash in H. Xu. (Omejen) razdelitveni vektor ?$(\zeta_{\alpha}, \ldots, \zeta_{\beta})$? je zaporedje, katerega členi ?$\zeta_r$? so števila ?$\mathscr{F}$?-WORM barvanj z natanko ?$r$? barvami, kjer je ?$\alpha \leq r \leq \beta$?. Obravnavamo razdelitvene vektorje polnih grafov in nekaterih 2-dreves. Pokažemo, da četudi 2-drevesa premorejo enake razdelitvene vektorje pri klasičnem pravilnem barvanju vozlišč, ki prepoveduje enobarvne ?$K_2$?, so njihovi razdelitveni vektorji v ?$K_3$?-WORM barvanju lahko različni.

29.05.2020