694 KB284 KB0 KB2022Brešar, BoštjanFerme, JasminaIX f, 128 str., 31 cmCOBISSID:104015875URN:URN:NBN:SI:doc-6QJ5VDR9slJ. Fermevisokošolska delabarvanjecoloringcritical graphcubic graphDisertacijedoctoral thesesdoktorske disertacijegraf SierpińskegaGrafikritičen grafkubični grafpacking chromatic critical graphpacking chromatic numberpacking chromatic-vertex critical graphpacking coloringpakirno barvanjepakirno kromatično kritičen grafpakirno kromatično številopakirno kromatično vozliščno-kritičen grafSierpiński graphSierpiński triangle graphtrikotnik SierpińskegaPakirna barvanja nekaterih razredov grafov z rekurzivno strukturo| doktorska disertacija|In this dissertation, packing colorings of graphs are studied. These colorings are among very well studied variants of graph colorings. The dissertation consists of three parts, in which we present solutions of 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 the basis of a given open question, its solution or their recursive structure is an important tool of proving 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 was 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 for them) 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 ofpacking chromatic critical graphs with small packing chromatic numbers and discuss packing chromatic critical block graphsV doktorski disertaciji obravnavamo pakirna barvanja grafov. Ta predstavljajo eno izmed zelo raziskovanih variacij barvanj vozlišč grafov. Doktorska disertacija je sestavljena iz treh delov, v sklopu katerih predstavimo ugotovitve, pridobljene pri razreševanju 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 pod kubič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 pod kubič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 grafeTEXTvisokošolska delatheses and dissertationsSlovenian National E-content AggregatorNational and University Library of SloveniaUniverza v Mariboru, Fakulteta za naravoslovje in matematiko