Na Oddelku za matematiko in računalništvo je doktoriral Marko Jakovac.

Naslov doktorske disertacije je Barvanja grafov Sierpińskega in b-barvanja. Opravljena je bila pod mentorstvom prof. dr. Sandija Klavžarja in somentorstvom doc. dr. Sergia Cabella Justa, komisijo ob zagovoru pa sta poleg mentorja in somentorja sestavljala še prof. dr. Uroš Milutinović in doc. dr. Iztok Peterin.

V disertaciji so obravnavani različni tipi grafov Sierpińskega (grafi Sierpińskega S(n,k), grafi trikotnikov Sierpińskega Sn, regularni grafi Sierpińskega S+(n,k) in S++(n, k)) ter podane natančne vrednosti kromatičnega števila in kromatičnega indeksa omenjenih grafov. Prav tako je podano celotno kromatično število grafov trikotnikov Sierpińskega.
V nadaljevanju je iz grafov Sierpińskega S(n,k) izpeljena nova 2-parametrična družina grafov S[n,k] imenovana posplošeni grafi trikotnikov Sierpińskega. Podano je število vozlišč in povezav grafov S[n,k]. Pokazano je tudi, da so grafi S[n,k] Hamiltonovi, kar ima za posledico, da so grafi trikotnikov Sierpińskega Sn Hamiltonovi. Določeno je tudi kromatično število grafov S[n,k].

Drugi del disertacije je v celoti posvečen b-barvanjem in iskanju b-kromatičnega števila nekaterih družin grafov. Določeno je b-kromatično število grafov Sierpińskega. Nadaljevanje je posvečeno regularnim grafom. Za kubične grafe je pokazano, da imajo vsi, razen štirih izjem, b-kromatično število 4. Med izjemami se pojavi tudi Petersenov graf. Pokazano je tudi, da ima vsak d-regularni graf na vsaj 2d3 vozliščih b-kromatično število d+1, da je b-kromatično število poljubnega d-regularnega grafa z ožino g=5 vsaj ⌊(d-1)/2⌋ in da vsak d-regularni graf, d≥6, s premerom vsaj d in brez 4-ciklov premore b-barvanje z d+1 barvami.

Zaključek disertacije je namenjen b-barvanjem krepkega, leksikografskega in direktnega produkta. Podanih je nekaj natančnih rezultatov produkta poti, ciklov, zvezd in polnih dvodelnih grafov. Dokazanih pa je tudi nekaj natančnih rezultatov, ko je eden izmed faktorjev poljuben. S pomočjo teh rezultatov je dokazano, da b-kromatično število krepkega, leksikografskega in direktnega produkta v splošnem ni navzgor omejeno z b-kromatičnim številom njegovih faktorjev.

To je šestindvajseti doktorat na Oddelku za matematiko in računalništvo.

Accessibility