Na Oddelku za matematiko in računalništvo je doktorirala Petra Šparl. Naslov doktorske disertacije je Posplošena barvanja in heksagonalni grafi. Opravljena je bila pod mentorskim vodstvom prof. dr. Janeza Žerovnika. Komisijo za zagovor sta poleg mentorja sestavljala še prof. dr. Aleksander Vesel in prof. dr. Tomaž Pisanski iz Fakultete za matematiko in fiziko Univerze v Ljubljani.
Petra Šparl v doktorski disertaciji obravnava različne posplošitve barvanja grafov, pri čemer se v večini primerov omeji na inducirane podgrafe trikotniške mreže ali heksagonalne grafe.
Podrobneje so obravnavani k-lokalni algoritmi za večbarvanje heksagonalnih grafov. Podana sta porazdeljen 2-lokalen 4/3-aproksimacijski algoritem za večbarvanje heksagonalnih grafov in porazdeljen 2-lokalen 5/4-aproksimacijski algoritem za večbarvanje heksagonalnih grafov brez trikotnikov.
Del disertacije je namenjen homomorfizmom grafov. Podrobneje je obravnavana C2k+1-pobarvljivost heksagonalnih grafov. Dokazano je, da je poljuben heksagonalen graf brez trikotnikov C5-pobarvljiv.
Podane so tudi zgornje meje za krožno in deljeno kromatično število heksagonalnih grafov brez trikotnikov.
Podrobneje so obravnavani k-lokalni algoritmi za večbarvanje heksagonalnih grafov. Podana sta porazdeljen 2-lokalen 4/3-aproksimacijski algoritem za večbarvanje heksagonalnih grafov in porazdeljen 2-lokalen 5/4-aproksimacijski algoritem za večbarvanje heksagonalnih grafov brez trikotnikov.
Del disertacije je namenjen homomorfizmom grafov. Podrobneje je obravnavana C2k+1-pobarvljivost heksagonalnih grafov. Dokazano je, da je poljuben heksagonalen graf brez trikotnikov C5-pobarvljiv.
Podane so tudi zgornje meje za krožno in deljeno kromatično število heksagonalnih grafov brez trikotnikov.
To je trinajsti doktorat iz matematike na našem oddelku.
