Zvezdni kromatični indeks grafa definiramo kot najmanjše možno število barv, s katerimi lahko pravilno obarvamo povezave grafa, tako da dobi vsaka pot ali cikel na štirih povezavah vsaj tri različne barve. Dokazana je "skoraj linearna" zgornja meja zvezdnega kromatičnega indeksa v odvisnosti od maksimalne stopnje grafa. Glede spodnje meje je za polne grafe reda n dokazana spodnja meja $2n(1+o(1))$. Za primer kubičnih grafov pa je dokazano, da ima njihov zvezdni kromatični indeks vrednost med 4 in 7. Vsi grafi, kjer je dosežena spodnja meja 4 so karakterizirani. Dokazi temeljijo na različnih tehnikah iz drugih področij matematike in so zato še posebej zanimivi.
COBISS.SI-ID: 16925273
V prvem delu članka poenotimo motivacijo in pristope k dvema zelo znanima spodnjima mejama za kromatično število grafa in zapišemo ti dve meji na način. ki omogoča enostavno razumevanje in implementacijo. V drugem delu članka pojasnimo, kako učinkovito izračunati ti dve meji z uporabo semidefinitnega programiranja in kako dobiti dobro barvanje iz optimalnih rešitev za obe meji.
COBISS.SI-ID: 2048193043
V tem članku analiziramo različne kopozitivne predstavitve problema delitve grafa in semidefinitnih poenostavitev, ki sledijo. Pokažemo, da sta kopozitivni predstavitvi, ki temeljita na Burerjevem in Povhovem rezultatu, ekvivalentni, in da obe porodita semidefinitni poenostavitvi, ki sta močnejši od Donath-Hoffmanove poenostavitve in od Wolkowicz-Zhao-ve poenostavitve.
COBISS.SI-ID: 1024318017