Pakirna barvanja nekaterih razredov grafov z rekurzivno strukturo

doktorska disertacija

Jasmina Ferme (Author), Boštjan Brešar (Mentor)

Abstract

V 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 grafe.

Keywords

doktorske disertacije;barvanje;pakirno barvanje;pakirno kromatično število;kubični graf;graf Sierpińskega;trikotnik Sierpińskega;kritičen graf;pakirno kromatično kritičen graf;pakirno kromatično vozliščno-kritičen graf;

Data

Language:	Slovenian
Year of publishing:	2022
Typology:	2.08 - Doctoral Dissertation
Organization:	UM FNM - Faculty of Natural Sciences and Mathematics
Publisher:	[J. Ferme]
UDC:	519.17(043.3)
COBISS:	104015875
Views:	214
Downloads:	25
Average score:	0 (0 votes)
Metadata:

Other data

Secondary language:	English
Secondary title:	Packing Coloring of Some Classes of Graphs with Recursive Structure
Secondary abstract:	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 graphs.
Secondary keywords:	doctoral theses;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;Grafični prikazi;Trikotnik;Univerzitetna in visokošolska dela;
Type (COBISS):	Doctoral dissertation
Pages:	IX f, 128 str.
ID:	13900142