Sodobne igre barvanj in sorodne igre na grafih

doktorska disertacija

Daša Štesl (Avtor), Boštjan Brešar (Mentor), Marko Jakovac (Komentor)

Povzetek

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 ne odvisnostne 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. Ob tem ugotovimo, da ne odvisnostno 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 - ne odvisnostno ter AB -ne odvisnostno igralno kromatično število. Med drugim obravnavamo vprašanje povezanosti grafov, ki so kritični glede na omenjene igralne invariante grafov, 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 igri dominacije s preprečevanjem. Določimo neodvisni dominantni števili s preprečevanjem za poti in cikle. Ob tem postavimo meje za obe variaciji omenjene igre ter karakteriziramo (povezane) grafe, ki dosežejo dobljeni meji. Dodatno opozorimo na tesno povezavo med neodvisno igro dominacije 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;disertacije;

Podatki

Jezik:	Slovenski jezik
Leto izida:	2022
Tipologija:	2.08 - Doktorska disertacija
Organizacija:	UM FNM - Fakulteta za naravoslovje in matematiko
Založnik:	D. Mesarič Štesl]
UDK:	519.17(043.3)
COBISS:	126226179
Št. ogledov:	13
Št. prenosov:	2
Ocena:	0 (0 glasov)
Metapodatki:

Ostali podatki

Sekundarni jezik:	Angleški jezik
Sekundarni naslov:	Contemporary coloring games and related games on graphs
Sekundarni povzetek:	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.
Sekundarne ključne besede:	dissertations;coloring game;indicated coloring game;competition-independence game;packing coloring game;Cartesian product;tree;vertex-critical graph;Teorija grafov;Grafi;Disertacije;Univerzitetna in visokošolska dela;
Vrsta dela (COBISS):	Doktorsko delo/naloga
Komentar na gradivo:	Univ. v Mariboru, Fak. za naravoslovje in matematiko, Oddelek za matematiko in računalništvo
Strani:	IX, 140 str.
ID:	15252402