VSE knjižnice (vzajemna bibliografsko-kataložna baza podatkov COBIB.SI)
  • Packing chromatic number versus chromatic and clique number
    Brešar, Boštjan ...
    Pakirno kromatično število ▫$\chi_{\rho}(G)$▫ grafa ▫$G$▫ je najmanjše pozitivno celo število ▫$k$▫, tako da lahko množico vozlišč grafa ▫$G$▫ razdelimo v množice ▫$V_i$▫, ▫$i \in [k]$▫, kjer je ... množica ▫$V_i$▫ t.i. ▫$i$▫-pakiranje. V članku za dane trojice pozitvnih celih števil ▫$(a,b,c)$▫ raziskujemo, ali obstaja graf ▫$G$▫, za katerega velja ▫$\omega(G) = a$▫, ▫$\chi(G) = b$▫, in ▫$\chi_{\rho}(G) = c$▫. Če je odgovor pritrdilen, pravimo, da je trojica ▫$(a, b, c)$▫ uresničljiva. Dokažemo, da iz ▫$ b=c\ge 3$▫ sledi ▫$a=b$▫ ter da trojice ▫$(2,k,k+1)$▫ in ▫$(2,k,k+2)$▫ niso uresničljive, brž ko je ▫$k\ge 4$▫. Nekateri izmed dobljenih rezultatov so izpeljani iz meja, ki jih dokažemo za pakirno kromatično število grafov Mycielskega. Za slednje grafe je dokazana tudi formula za nedvisnostno število. Dokazana je tudi spodna meja za ▫$\chi_{\rho}(G)$▫, ki je izražena z ▫$\Delta(G)$▫ in ▫$\alpha(G)$▫.
    Vir: Aequationes mathematicae. - ISSN 0001-9054 (Vol. 92, iss. 3, 2018, str. 497-513)
    Vrsta gradiva - članek, sestavni del
    Leto - 2018
    Jezik - angleški
    COBISS.SI-ID - 18370905

    Povezava(-e):

    https://doi.org/10.1007/s00010-017-0520-9

vir: Aequationes mathematicae. - ISSN 0001-9054 (Vol. 92, iss. 3, 2018, str. 497-513)
loading ...
loading ...
loading ...

Vnos na polico