VSE knjižnice (vzajemna bibliografsko-kataložna baza podatkov COBIB.SI)
  • Packing chromatic number, ▫$(1,1,2,2)$▫-colorings, and characterizing the Petersen graph
    Brešar, Boštjan ...
    Pakirno kromatično število ▫$\chi_{\rho}(G)$▫ grafa ▫$G$▫ je najmanjše celo število ▫$k$▫, tako da lahko množico vozlišč grafa ▫$G$▫ razdelimo v množice ▫$\Pi_1,\ldots,\Pi_k$▫, kjer je ▫$\Pi_i$▫ (▫$i ... \in [k]$▫) ▫$i$▫-pakiranje. Postavljena in raziskovana je naslednja domneva: če je ▫$G$▫ podkubičen graf, potem je ▫$\chi_{\rho}(S(G))\le 5$▫, kjer je ▫$S(G)$▫ subdivizija grafa ▫$G$▫. Domneva je dokazana za vse posplošene prizme ciklov. Da dokažemo ta rezultat, je tudi dokazano, da če je ▫$G$▫ posplošena prizma cikla, potem je▫$G$▫ ▫$(1,1,2,2)$▫-obarvljiv natanko tedaj, ko ▫$G$▫ ni Petersenov graf. Veljavnost domneve je nadalje dokazana za grafe, ki jih lahko dobimo iz posplošenih prizm tako, da enega izmed dveh ▫$n$▫-ciklov nadomestimo z unijo ciklov, med katerimi je največ en 5-cikel. Obravnavano je tudi pakirno kromatično število grafov dobljenih s subdivizijo vsake izmed njegovih povezan enakokrat.
    Vir: Aequationes mathematicae. - ISSN 0001-9054 (Vol. 91, iss. 1, 2017, str. 169-184)
    Vrsta gradiva - članek, sestavni del
    Leto - 2017
    Jezik - angleški
    COBISS.SI-ID - 17889113

    Povezava(-e):

    http://dx.doi.org/10.1007/s00010-016-0461-8

vir: Aequationes mathematicae. - ISSN 0001-9054 (Vol. 91, iss. 1, 2017, str. 169-184)
loading ...
loading ...
loading ...

Vnos na polico