20.500.12556/DKUM-81673 Sodobne igre barvanj in sorodne igre na grafih Contemporary coloring games and related games on graphs 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. 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. igra barvanja indicirana igra barvanja neodvisnostna igra barvanja neodvisna dominacijska igra pakirna igra barvanja kartezični produkt drevo vozliščno kritičen graf coloring game indicated coloring game independence coloring game competition-independence game packing coloring game Cartesian product tree vertex-critical graph true true false D. Mesarič Štesl] Slovenski jezik Angleški jezik Doktorsko delo/naloga 2022-05-09 13:44:31 2022-10-25 16:15:28 2022-10-26 03:24:30 0000-00-00 00:00:00 2022 0 [Maribor 0 0000-00-00 NiDoloceno NiDoloceno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 519.17(043.3) 126226179 DOK_Mesaric_Stesl_Dasa_2022.pdf DOK_Mesaric_Stesl_Dasa_2022.pdf 1 2D33F8172136737AEE8132A259EF0A06 70abf6046564140e32e59f5dda0d90aa47cd66f48a9b4e203baec91503c3468c 40906f74-4007-11ed-a889-00155d000105 https://dk.um.si/Dokument.php?lang=slv&id=163626 Fakulteta za naravoslovje in matematiko 0 0 0