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
Obravnavamo razred grafov, ki leži strogo med razredoma grafov roda (največ) $k-1$ in $k$. Za fiksno orientabilno ploskev $\mathbb{S}_k$ roda $k$ naj bo $\mathcal{A}_{xy}^k$ za minorje zaprt razred grafov s terminaloma $x$ in $y$, ki so vložljivi v $\mathbb{S}_{k-1}$ ali pa premorejo vložitev $\Pi$ v $\mathbb{S}_k$, ki vsebuje $\Pi$-lice, na katerem $x$ in $y$ nastopata dvakrat v alternirajočem vrstnem redu. V članku obravnavamo ovire za razrede $\mathcal{A}_{xy}^k$. V posebnem primeru podamo popoln seznam ovir za $\mathcal{A}_xy}^1$.
COBISS.SI-ID: 17761369
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