1. Pakirna barvanja nekaterih razredov grafov z rekurzivno strukturo : doktorska disertacijaJasmina Ferme, 2022, doktorska disertacija Opis: 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.
Ključne besede: 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
Objavljeno v DKUM: 07.04.2022; Ogledov: 1015; Prenosov: 86
 Celotno besedilo (694,86 KB) |
2. Nekatere s pakiranji povezane lastnosti grafovDragana Božović, 2020, doktorska disertacija Opis: V disertaciji se ukvarjamo z različnimi problemi, povezanimi s pakiranji. Disertacija je sestavljena iz štirih delov.
Prvi del je namenjen grafom, ki imajo enolično pakirno množico največje moči. Najprej predstavimo nekatere lastnosti teh grafov. Nato podamo še dve karakterizaciji dreves z enolično pakirno množico.
V drugem delu vpeljemo pojem dimenzije incidenčnosti, ki je neposredno povezana z 2-pakirnim številom grafa, in določimo formulo za njen izračun. Dokažemo, da je problem iskanja incidenčne dimenzije grafa v splošnem NP-poln.
Tretji del namenimo pakirnemu kromatičnemu številu leksikografskega produkta grafov. Določimo njegovo spodnjo in zgornjo mejo ter izboljšano zgornjo mejo za primer, ko je prvi faktor v produktu izomorfen poti.
V zadnjem delu se posvetimo učinkoviti odprti dominaciji produktov digrafov. Okarakteriziramo učinkovito odprto dominirane direktne in leksikografske produkte digrafov. Pri kartezičnem produktu okarakteriziramo tiste, kjer je prvi faktor usmerjena pot, usmerjen cikel ali zvezda z enim izvorom. Predstavimo tudi karakterizacijo učinkovito odprto dominiranega krepkega produkta, katerega temeljni graf obeh faktorjev je monocikličen graf.
Ključne besede: pakirna množica, enolično največje pakiranje, dimenzija incidenčnosti, generator incidenčnosti, pakirno kromatično število, leksikografski produkt grafov, učinkovita odprta dominacija, usmerjeni grafi, produkti usmerjenih grafov
Objavljeno v DKUM: 27.11.2020; Ogledov: 1563; Prenosov: 197
Celotno besedilo (753,30 KB) |
3. (d, n)-pakirno barvanje za posplošene grafe Sierpińskega : magistrsko deloAnže Jeromel, 2019, magistrsko delo Opis: V magistrski nalogi so opisani grafi Sierpińskega in njihove posplošitve, (d, n)-pakirno barvanje grafov ter računsko iskanje (d, n)-pakirnih kromatičnih števil. Razvili smo algoritem za generiranje grafov Sierpińskega z osnovo 4 ter implementirali štiri metode barvanja grafov. Našli smo točna (d, n)-pakirna kromatična števila za različne kombinacije (d, n) pri grafih stopnje 2, pri grafih višjih stopenj pa njihove zgornje meje. Prav tako smo našli točna (1, 1)-pakirna kromatična števila dveh izbranih posplošenih grafov Sierpińskega do vključno stopnje 5.
Ključne besede: Sierpiński, pakirno barvanje, pakirno kromatično število
Objavljeno v DKUM: 04.06.2019; Ogledov: 1488; Prenosov: 123
Celotno besedilo (4,27 MB) |
4. On the packing chromatic number of Cartesian products, hexagonal lattice, and treesBoštjan Brešar, Sandi Klavžar, Douglas F. Rall, 2007, izvirni znanstveni članek Opis: Pakirno kromatično število ▫$chi_{rho}(G)$▫ grafa ▫$G$▫ je najmanjše število ▫$k$▫, tako da lahko množico vozlišč grafa ▫$G$▫ razbijemo v pakiranja s paroma različnimi širinami. Dobljenih je več spodnjih in zgornjih meja za pakirno kromatično število kartezičnega produkta grafov. Dokazano je, da pakirno kromatično število šestkotniške mreže leži med 6 in 8. Optimalne spodnje in zgornje meje so dokazane za subdividirane grafe. Obravnavana so tudi drevesa ter vpeljana monotona barvanja.
Ključne besede: matematika, teorija grafov, pakirno kromatično število, kartezični produkt grafov, šestkotniška mreža, subdividiran graf, drevo, računska zahtevnost, mathematics, graph theory, packing chromatic number, Cartesian product of graphs, hexagonal lattice, subdivision graph, tree, computational complexity
Objavljeno v DKUM: 10.07.2015; Ogledov: 1320; Prenosov: 158
 Povezava na celotno besedilo |
