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
Poglavje v referenčni izdaji Handbook of Graph Theory, ki je izšla pri CRC Press. V poglavju so prikazani glavni rezultati teorije grafovskih limit: grafoni, gostota homomorfizmov, konvergenčna zaporedja končnih grafov in njihovih limit, metrični prostor grafonov, Szemeredijeva lema o regularnosti in aproksimacija grafonov z uteženimi grafi, slučajni grafi, ki ustrezajo grafonu, grafovski parametri in pripadajoče matrike, ekstremalna teorija grafov in algebra kvantnih grafov.
COBISS.SI-ID: 16921945
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$ spektralno $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
V članku je pokazano, da so za poljubno družino grafov, ki je zaprta za minorje, naslednji pogoji primerljivo ekvivalentni za vsak graf v tej družini: (a) graf ima mnogo velikih lastnih vrednosti; (b) graf ima mnogo velikih negativnih lastnih vrednosti; (c) graf ima mnogo vozlišč visoke stopnje. Primerljiva ekvivalenca je izražena kvantitativno preko pogojev, kako velike so lastne vrednosti in koliko jih je. Vsaka smer ekvivalence lahko to velikost spremeni največ za konstantni faktor, ki je odvisen le od družine grafov in ne od posamenih članov družine.
COBISS.SI-ID: 16648537
Ob predpostavki P$\ne$NP pokažemo naslednji izrek: obstaja taka konstanta $c ) 1$, da ni nobenega $c$-aproksimacijskega polinomskega algoritma za računanje prekrižnega števila grafa. Rezultat velja tudi za 3-regularne grafe.
COBISS.SI-ID: 16340313