Sodobne igre barvanj in sorodne igre na grafih

Štesl, Daša

| | SLO | ENG | Piškotki in zasebnost

Večja pisava | Manjša pisava

Prva stran > Izpis gradiva

Izpis gradiva

Naslov:	Sodobne igre barvanj in sorodne igre na grafih
Avtorji:	ID Štesl, Daša (Avtor) ID Brešar, Boštjan (Mentor) Več o mentorju... ID Jakovac, Marko (Komentor)
Datoteke:	DOK_Mesaric_Stesl_Dasa_2022.pdf (614,26 KB) MD5: 2D33F8172136737AEE8132A259EF0A06
Jezik:	Slovenski jezik
Vrsta gradiva:	Doktorsko delo/naloga
Tipologija:	2.08 - Doktorska disertacija
Organizacija:	FNM - Fakulteta za naravoslovje in matematiko
Opis:	V doktorski disertaciji obravnavamo v zadnjih letih vpeljane variacije klasične igre barvanja in njim sorodne igre na grafih. Doktorsko delo sestoji iz štirih delov, znotraj katerih predstavimo nova spoznanja na omenjeno temo. V prvem delu disertacije obravnavamo indicirano igro barvanja kartezičnih produktov grafov. Natančneje, določimo indicirano igralno kromatično število kartezičnih produktov grafov, katerih indicirano kromatično število znaša 3, s polnim dvodelnim grafom. Dodatno obravnavamo indicirano kromatično število kartezičnih produktov bločnih grafov in dreves ter indicirano kromatično število kartezičnega produkta dveh ciklov. V drugem delu disertacije se posvetimo študiji štirih variacij neodvisnostne igre barvanja, ki so posebna oblika klasične igre barvanja, pri kateri igralca ne preideta na višjo raven, dokler ne izčrpata vseh možnosti za uporabo dane barve. Dobljene igralne invariante primerjamo med seboj in s klasičnim igralnim kromatičnim številom. Poleg tega ugotovimo, da neodvisnostno igralno kromatično število v razredu dreves ni omejeno. V tretjem delu preučujemo vozliščno kritične grafe glede na klasično igralno kromatično število, glede na indicirano kromatično število in glede na A-neodvisnostno ter AB-neodvisnostno igralno kromatično število. Med drugim obravnavamo vprašanje povezanosti grafov, ki so kritični glede na omenjene igralne grafovske invariante, obnašanje dane igralne invariante ob odstranitvi poljubnega vozlišča iz igralno vozliščno kritičnega grafa ter karakteriziramo igralno vozliščno kritične grafe, ki imajo majhno vrednost pripadajoče invariante. Zadnji del doktorske disertacije posvetimo neodvisni dominacijski igri s preprečevanjem. Določimo neodvisni dominantni števili s preprečevanjem za poti in cikle. Poleg tega postavimo meje za obe variaciji omenjene igre ter karakteriziramo (povezane) grafe, ki dosežejo dobljeni meji. Dodatno opozorimo na tesno povezavo med neodvisno dominacijsko igro s preprečevanjem in pakirno igro barvanja v grafih z diametrom 2.
Ključne besede:	igra barvanja, indicirana igra barvanja, neodvisnostna igra barvanja, neodvisna dominacijska igra, pakirna igra barvanja, kartezični produkt, drevo, vozliščno kritičen graf
Kraj izida:	[Maribor
Založnik:	D. Mesarič Štesl]
Leto izida:	2022
PID:	20.500.12556/DKUM-81673
UDK:	519.17(043.3)
COBISS.SI-ID:	126226179
Datum objave v DKUM:	25.10.2022
Število ogledov:	907
Število prenosov:	85
Metapodatki:
Področja:	FNM
:	Kopiraj citat

Skupna ocena:	(0 glasov)
Vaša ocena:	Ocenjevanje je dovoljeno samo prijavljenim uporabnikom.
Objavi na:

Postavite miškin kazalec na naslov za izpis povzetka. Klik na naslov izpiše podrobnosti ali sproži prenos.

Licence

Licenca:	CC BY-NC-ND 4.0, Creative Commons Priznanje avtorstva-Nekomercialno-Brez predelav 4.0 Mednarodna

Povezava:	http://creativecommons.org/licenses/by-nc-nd/4.0/deed.sl
Opis:	Najbolj omejujoča licenca Creative Commons. Uporabniki lahko prenesejo in delijo delo v nekomercialne namene in ga ne smejo uporabiti za nobene druge namene.
Začetek licenciranja:	09.05.2022

Sekundarni jezik

Jezik:	Angleški jezik
Naslov:	Contemporary coloring games and related games on graphs
Opis:	In this dissertation, we consider several recent variations of the classical coloring game, and some related games on graphs. The dissertation consists of four parts within which we present new insights on the mentioned topics. In the first part of the dissertation, we consider indicated coloring game on Cartesian products of graphs. More precisely, we determine the indicated game chromatic number of Cartesian products of graphs, whose indicated game chromatic number equals $3$, with complete bipartite graphs. In addition, we study the indicated game chromatic number of Cartesian products of block graphs and trees, and the indicated game chromatic number of Cartesian product of two cycles. In the second part of the dissertation, we study four variations of the independence coloring game, which is a special variation of the classical coloring game in which the players do not move to a higher level until they have exhausted all possibilities of using a given color. We compare the obtained invariants of the independence game chromatic number among themselves and with the classical game chromatic number. In addition, we prove that the independence game chromatic number in the class of trees is unbounded. In the third part, we study the vertex-critical graphs with respect to the classical game chromatic number, with respect to the indicated chromatic number, and with respect to the A-independence and the AB-independence game chromatic number. Among other results, we discuss the connectivity of graphs that are vertex-critical with respect to the mentioned game chromatic invariants, consider the relation between game chromatic invariants of critical graphs and their vertex-deleted sub\-graphs, and characterize the game chromatic vertex-critical graphs with small value of the associated invariant. The last part of the dissertation is dedicated to the competition-independence game with prevention. We determine the competition-independence numbers with prevention for paths and cycles. In addition, we obtain bounds for both variations of the mentioned game and characterize (connected) graphs that attain the obtained bounds. We also observe that the competition-independence game with prevention and the packing coloring game are closely related in graphs with diameter 2.
Ključne besede:	coloring game, indicated coloring game, independence coloring game, competition-independence game, packing coloring game, Cartesian product, tree, vertex-critical graph

Komentarji

Dodaj komentar

Za komentiranje se morate prijaviti.

Komentarji (0)

0 - 0 / 0

Ni komentarjev!

Nazaj