VSE knjižnice (vzajemna bibliografsko-kataložna baza podatkov COBIB.SI)
  • On the number of maximal independent sets in minimum colorings of split graphs
    Brešar, Boštjan ; Movarraei, Nazanin
    Največje število barvnih razredov, ki so dominantne množice (ali, ekvivaletno, ki so maksimalne neodvisne množice) med vsemi ▫$\chi(G)$▫-barvanji grafa ▫$G$▫ se imenuje dominantno-▫$\chi$▫-barvno ... število grafa ▫$G$▫ in se označi z ▫$d_{\chi}(G)$▫. Arumugam et al. (2011) so dokazali, da je določitev, ali velja ▫$d_{\chi}(G)\ge 2$▫, NP-poln problem celo v 3-kromatičnih grafih. V tem članku dokažemo, da je v razcepljenem grafu dominantno-▫$\chi$▫-barvno število enako 1 natanko tedaj, ko je njegovo dominantno število večje od 2. Medtem ko lahko takšne grafe učinkovito prepoznamo, pa v članku dokažemo, da je odločitvena verzija problema dominantnega-▫$\chi$▫-barvnega števila v razcepljenih grafih z dominantnim številom največ 2 NP-poln problem. Predstavimo tudi rezultate o obstoju razcepljenih grafov, ki dosegajo predpisane vrednosti dominantnih-▫$\chi$▫-barvnih števil in nekaterih drugih relevantnih parametrov.
    Vir: Discrete applied mathematics. - ISSN 0166-218X (Vol. 247, Oct. 2018, str. 352-356)
    Vrsta gradiva - članek, sestavni del ; neleposlovje za odrasle
    Leto - 2018
    Jezik - angleški
    COBISS.SI-ID - 18422873

    Povezava(-e):

    https://doi.org/10.1016/j.dam.2018.03.083
    DOI

Vnos na polico