Sum-list-colouring of theta-hypergraphs

angleški

2022

letnik 22, številka 1

?$\theta $?-hipergrafi   hipergrafi   vsotno seznamsko barvanje

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

Če sta dana hipergraf ?$\mathcal{H}$? in funkcija ?$f:V( \mathcal{H}) \rightarrow \mathbb{N} $?, pravimo, da je ?$\mathcal{H}$? ?$f$?-izbiren, če obstaja pravilno vozliščno barvanje ?$\phi$?, pri katerem je ?$\phi(v) \in L(v)$? za vsa vozlišča ?$v\in V(\mathcal{H})$?, kjer je ?$L:V( \mathcal{H}) \rightarrow 2^{\mathbb{N}}$? poljubna dodelitev ?$f(v)$? barv vozlišča ?$v$?. Vsotno izbirni indeks ?$\chi_{sc}(\mathcal{H})$? hipergrafa ?$\mathcal{H}$? je definiran kot minimum vsote ?$\sum_{v \in V(\mathcal{H})} f(v)$? po vseh funkcijah ?$f$?, za katere je ?$\mathcal{H}$? ?$f$?-izbiren. Trivialna zgornja meja za ?$\chi_{sc} (\mathcal{H})$? je ?$|V(\mathcal{H}|) + |\mathcal{E} \mathcal{H})|$?. Razred ?$\Gamma_{sc}$? hipergrafov, ki dosežejo to mejo, je induciran hereditarno. Analiziramo nekaj lastnosti hipergrafov iz razreda ?$\Gamma_{sc}$?, pa tudi lastnosti hipergrafov iz razreda prepovedanih hipergrafov za ?$\Gamma_{sc}$?. Karakteriziramo vse ?$\theta$?-hipergrafe iz razreda ?$\Gamma_{sc}$?, od tod pa dobimo tudi karakterizacijo vseh ?$\theta$?-hipergrafov, ki so prepovedani za ?$\Gamma_{sc}$?.

22.11.2022