Akademska digitalna zbirka SLovenije - logo
(UL)
  • List-colouring squares of sparse subcubic graphs
    Dvořák, Zdeněk ; Škrekovski, Riste ; Tancer, Martin
    Problem barvanja kvadrata grafa je v tesni zvezi z razdaljnim označevanjem grafov, ki je predmet intenzivnega raziskovanja v zadnjem času. Problem obravnavamo na redkih subkubičnih grafih. Pokažemo, ... da je izbirljivost ▫$\chi_\ell(G^2)$▫ kvadrata subkubičnega grafa z maksimalno povprečno stopnjo ▫$d$▫ največ 4, če je ▫$d < 24/11$▫ in ▫$G$▫ ne vsebuje 5-ciklov, ▫$\chi_\ell(G^2)$▫ je največ 5 za ▫$d < 7/3$▫ in je največ 6 za ▫$d < 5/2$▫. Wegnerjeva hipoteza trdi, da je kromatično število kvadrata subkubičnega ravninskega grafa največ 7. Naj bo ▫$G$▫ ravninski graf z notranjim obsegom ▫$g$▫. Iz našega rezultata sledi, da je ▫$\chi_\ell(G^2)$▫ največ 4 za ▫$g \ge 24$▫, največ 5 za ▫$g \ge 14$▫ in največ 6 za ▫$g \ge 10$▫. Določili smo spodnji meji: ravninski subkubični graf ▫$G_1$▫ z notranjim obsegom 9 in ▫$\chi(G_1^2) = 5$▫ ter ravninski subkubični graf ▫$G_2$▫ z notranjim obsegom 5 in ▫$\chi(G_2^2) = 6$▫. Posledično dokažemo, da je problem 4-barvanja kvadrata subkubičnega ravninskega grafa z notranjim obsegom ▫$g=9$▫ NP-težek problem. Članek zaključimo z nekaj odprtimi vprašanji.
    Vir: Preprint series. - ISSN 1318-4865 (Vol. 43, št. 985, 2005, str. 1-30)
    Vrsta gradiva - članek, sestavni del
    Leto - 2005
    Jezik - angleški
    COBISS.SI-ID - 13779033

    Povezava(-e):

    http://www.imfm.si/preprinti/PDF/00985.pdf

vir: Preprint series. - ISSN 1318-4865 (Vol. 43, št. 985, 2005, str. 1-30)

loading ...
loading ...
loading ...

Vnos na polico