Dokazano je, da za vsak $c\ge 13$ in $d\ge 1$ obstajajo c-ktitični grafi (za prekrižno število), ki imajo maksimalno stopnjo vsaj d. Dokazano je tudi, da za d ( 13 takšni grafi ne obstajajo. S tem je dokončno razjasnjena Richterjeva hipoteza maksimalne stopnje, ki sta jo leta 2010 ovrgla Dvořák in Mohar. Presenetljivo pa je, da hipoteza velja za $c\le 12$.
COBISS.SI-ID: 18858585
Podamo nov dokaz, da je vsak ravninski graf seznamsko 5-pobarvljiv in ga uporabimo, da pokažemo, da je vsaka risba grafa v ravnini, pri kateri so vsa križanja paroma na razdalji vsaj 15, seznamsko 5-pobarvljiva. Hkrati dovolimo, da imajo nekatere točke sezname barv velikosti 4, če so te točke med sabo paroma daleč in če so daleč od križanj
COBISS.SI-ID: 18214489
V prispevku ki e bil sprejet na FOCS (2018), je razvita polinomska aproksimacijska shema (PTAS) za problem določanja roda grafa v primerzu gostih grafov, Algoritem ima kvadratično časovno zahtevnost, njegova nadgradnja, ki tudi poišče vložitev, pa ima značilnosti verjetnostnih algoritmov.
COBISS.SI-ID: 18855001
Obravnavamo 1-ravninske risbe grafov, kjer je 1-ravninska risba grafa definirana kot risba grafa v ravnini, v kateri je vsaka povezava udeležena v največ enem križanju. Ker vemo, da je problem NP-težek obravnavamo parametrično zahtevnost glede na velikost najmanjšega pokritja, drevesno globino in ciklomatično število. Za te parametre pokažemo, da je problem parametrično dostopen. Problem ostane NP-težak v primeru omejene pasovne širine, preme širine in drevesne širine.
COBISS.SI-ID: 18208345
Uvedemo dve novi delni urejenosti na standardnih Young tabelah z dano particijsko obliko, po analogiji z močnimi in šibkimi Bruhatovimi urejenostmi na permutacijah. Obe postavi sta razvrščeni po statistiki glavnega indeksa, ki se nadomesti s fiksnim premikom. Obstoj takšnih delno urejenih struktur nam omogoča razvrstitev realizabilnih statistik glavnih indeksov na standardne tabele poljubnih ravnih oblik in določenih poševnih oblik. Z izrekom Lusztig-Stanleyja [R. P. Stanley, bik. Am. Matematika. Soc., Nova ser. 1, 475-511 (1979) trditev 4.11], si lahko to razvrstitev razložimo kot določitev, katere ireducibilne reprezentacije simetrične grupe obstajajo, v katerih homogenih komponentah ustrezne koinvariantne algebre, kar krepi nedavni rezultat tretjega avtorja za glavni modularni indeks. Naš pristop je prepoznati vzorce v standardnih tabelah, ki omogočajo spremembo padajočih množic na kontroliran način. Z delom G. Lusztiga [Izum. Matematika. 43, 125–175 (1977] in JR Stembridge [Pac. J. Math. 140, št. 2, 353–396 (1989)], se razlogi raztezajo na klasifikacijo vseh ničelnih lažnih stopenj kovavariantnih algebr za končne kompleksne zrcalnih grup v neskončni družini Shephard-Toddovih grup.
COBISS.SI-ID: 24348675