V članku so podane zgornje meje za degenerirano in zvezdno kromatično število in za njuno skupno posplošitev v odvisnosti od roda grafov. Kot pomožno orodje je dokazana naslednja posplošitev rezultata, ki ga je dokazal Fertin s soavtorji za zvezdno kromatično število. Če je $G$ graf z maksimalno stopnjo $\Delta$, potem ima $G$ degenerirano zvezdno barvanje z $O(\Delta^{3/2})$ barvami. Ta rezultat je uporabljen v dokazu glavnega izreka, ki pravi, da ima vsak graf roda $g$ degenerirano zvezdno barvanje z $O(g^{3/5})$ barvami. Dodani so primeri, ki dokazujajo, da so dobljene ocene optimalne do logaritemskega faktorja.
COBISS.SI-ID: 16199769
Znano je, da spektralni radij drevesa maksimalne stopnje $\Delta$ nikoli ne presega vrednosti $2\sqrt{\Delta-1}$. Znana je tudi posplošitev tega dejstva na poljubne ravninske grafe in na $d$-degenerirane grafe. Ti rezultati so motivacija za uvedbo novega parametra. Pravimo, da je graf $G$ spectralno $d$-degeneriran, kadar ima vsak njegov podgraf $H$ spektralni radij manjši od $\sqrt{d\Delta(H)}$. Dokazan je šibki obrat zgoraj omenjenih rezultatov, ki pove, da ima vsak spektralno $d$-degeneriran graf $G$ vozlišče, ki je stopnje kvečjemu $4d\log_2(\Delta(G)/d)$ (če je $\Delta(G) \ge 2d$). V tej oceni se odvisnosti od $\Delta$ ne da odpraviti, kar je dokazano z verjetnostno konstrukcijo posebnih primerov. Dokazano je tudi, da je odločitveni problem, ali je dani graf spektralno $d$-degeneriran, co-NP-poln.
COBISS.SI-ID: 16410457
Naj bo $G$ neutežen graf kompleksnosti $n$, ki je vložen v ploskev roda $g$. Prikazan je izboljšani algoritem za določanje dolžine najkrajšega nestisljivega in najkrajšega neseparirajočega cikla v grafu. Za vsako naravno število $k$ lahko najdemo tak cikel v času $O(gnk)$, če je njegova dolžina kvečjemu $k$. V nasprotnem primeru pa ugotovimo, da je dolžina večja od $k$. Tako za poljubno izbrano ploskev lahko preverimo v linearnem času, če je povezavna ali celična širina vloženega grafa večja od $k$. Prikazan je tudi aproksimacijski algoritem za iskanje najkrajšega netrivialnega cikla. Pri poljubnem danem parametru $\varepsilon$ ($0( \varepsilon ( 1$) dobimo v času $O(gn/\varepsilon)$ netrivialni cikel, katerega dolžina je kvečjemu za faktor $1+\varepsilon$ večja od najkrajšega takega cikla.
COBISS.SI-ID: 16093017