20.500.12556/DKUM-81029 Pakirna barvanja nekaterih razredov grafov z rekurzivno strukturo doktorska disertacija Packing Coloring of Some Classes of Graphs with Recursive Structure V doktorski disertaciji obravnavamo pakirna barvanja grafov. Ta predstavljajo eno izmed zelo raziskovanih variacij barvanj grafov. Doktorska disertacija je sestavljena iz treh delov, v sklopu katerih predstavimo rešitve različnih problemov v zvezi s pakirnimi barvanji. Omenjene probleme povezuje dejstvo, da pri njihovi obravnavi nastopajo grafi z rekurzivno strukturo. Ti predstavljajo temelj danega odprtega vprašanja, rešitev slednjega ali pa je njihova rekurzivna zgradba pomembno sredstvo pri dokazovanju spoznanj. V prvem delu disertacije predstavimo neskončno družino podkubičnih grafov z neomejenim pakirnim kromatičnim številom. Dodatna lastnost omenjene družine grafov je njena rekurzivna zgradba. S predstavitvijo omenjene družine grafov dopolnimo rešitev več let odprtega vprašanja glede omejenosti pakirnega kromatičnega števila v družini podkubičnih grafov. V drugem delu disertacije določamo pakirna kromatična števila (oziroma meje zanje) grafov tipa Sierpińskega, ki sodijo med najbolj znane razrede grafov z rekurzivno oziroma fraktalno strukturo. Omejimo se na obravnavo grafov Sierpińskega, posplošenih grafov Sierpińskega ter trikotnikov Sierpińskega. Zadnji del doktorske disertacije namenjamo obravnavi grafov, ki so kritični za pakirno kromatično število. Med drugim podamo karakterizacije pakirno kromatično kritičnih grafov z majhnimi pakirnimi kromatičnimi števili ter obravnavamo pakirno kromatično kritične bločne grafe. This dissertation examines the packing colorings of graphs. These colorings are among the well-studied variants of graph colorings. The dissertation consists of three parts, in which we present the solutions to various problems related to packing colorings. The common ground of the mentioned problems is that in their treatment graphs with a recursive structure appear. These graphs are either the basis of a given open question, its solution, or their recursive structure is an important tool in proving the results. In the first part of the dissertation, we present an infinite family of subcubic graphs with unbounded packing chromatic number. An additional property of the mentioned family of graphs is its recursive structure. By providing this family of graphs, we complete the solution to a question that has been open for several years regarding the boundedness of the packing chromatic number in the family of subcubic graphs. In the second part, we determine the packing chromatic numbers (or bounds) of Sierpiński-type graphs, which form a well-known class of graphs with recursive (fractal) structure. We consider Sierpiński graphs, generalized Sierpiński graphs, and Sierpiński triangle graphs. The last part of the dissertation is devoted to the graphs that are critical for the packing chromatic number. Among other things, we present characterizations of packing chromatic critical graphs with small packing chromatic numbers, and discuss packing chromatic critical block graphs. Barvanje pakirno barvanje pakirno kromatično število kubični graf graf Sierpińskega trikotnik Sierpińskega kritičen graf pakirno kromatično-vozliščno kritičen graf pakirno kromatično kritičen graf Coloring packing coloring packing chromatic number cubic graph Sierpiński graph Sierpiński triangle graph critical graph packing chromatic-vertex critical graph packing chromatic critical graph true true false [J. Ferme] Slovenski jezik Angleški jezik Doktorsko delo/naloga 2021-12-09 04:34:42 2022-04-07 11:44:43 2022-08-10 00:15:40 0000-00-00 00:00:00 2022 0 Maribor 0 Maribor IX f, 128 str. 0000-00-00 NiDoloceno NiDoloceno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 519.17(043.3) 104015875 DOK_Ferme_Jasmina_2022.pdf DOK_Ferme_Jasmina_2022.pdf 1 2866D749B21DE5FF38263EB10EDF3847 076394f725fe5937c9747c543f7f59e4ee7ec5a47f573906f14548fee907e33f 70269f61-a905-11ec-ab4c-00155d000105 20.500.12556/dkum/20522540-fcd8-4081-b79e-c736eee48110 https://dk.um.si/Dokument.php?lang=slv&id=156921 Fakulteta za naravoslovje in matematiko 0 0 0