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. The b-chromatic number of cubic graphsMarko Jakovac, Sandi Klavžar, 2010, izvirni znanstveni članek Opis: b-Kromatično število grafa ▫$G$▫ je največje celo število, za katero obstaja dobro ▫$k$▫-barvanje, v katerem vsak barvni razred vsebuje vsaj eno vozlišče, ki je sosednje z vsemi drugimi barvnimi razredi. Dokazano je, da je b-kromatično število kubičnih grafov enako 4 razen za Petersenov graf, ▫$K_{3,3}$▫, prizmo nad ▫$K_3$▫, in še en sporadičen primer na 10 vozliščih.
Ključne besede: teorija grafov, kromatično število, b-kromatično število, kubični graf, Petersenov graf, graph theory, chromatic number, b-chromatic number, cubic graph, Petersen graph
Objavljeno v DKUM: 10.07.2015; Ogledov: 1048; Prenosov: 95
 Povezava na celotno besedilo |
3. On cubic and edge-critical isometric subgraphs of hypercubesC. Paul Bonnington, Sandi Klavžar, Alenka Lipovec, 2002 Opis: Predstavljene so vse kubične delne kocke do 30 točk in vse po povezavah kritične delne kocke do 14 točk. Seznama sta bila potrjena z računalniškim iskanjem. Konstruirane so tudi netrivialne kubične delne kocke na 36, 42 in 48 točkah.
Ključne besede: matematika, teorija grafov, delna kocka, hiperkocka, kubični graf, računalniško iskanje, mathematics, graph theory, partial cube, hypercube, cubic graph, computer searching
Objavljeno v DKUM: 10.07.2015; Ogledov: 1207; Prenosov: 39
Povezava na celotno besedilo |
