VSE knjižnice (vzajemna bibliografsko-kataložna baza podatkov COBIB.SI)
  • The circular chromatic number of a digraph
    Bokal, Drago, 1978- ...
    Definirano je krožno kromatično število ▫$\chi_c$▫, pokazani so razni osnovni rezultati. Ti potrdijo, da je teorija barvanj digrafov podobna teoriji barvanj usmerjenih grafov, pri čemer neodvisne ... množice nadomestimo z acikličnimi. Ker imajo usmerjeni ▫$k$▫-cikli krožno kromatično število enako ▫$k/(k-1)$▫ za ▫$k \ge 2$▫, so mogoče vrednosti ▫$\chi_c$▫ tudi med 1 in 2. Pokažemo, da ▫$\chi_c$▫ lahko zavzame vse racionalne vrednosti, večje od 1. Poleg tega obstajajo digrafi s poljubno veliko dolžino najkrajšega usmerjenega cikla in hkrati s poljubno visokim krožnim kromatičnim številom. Problem odločanja, ali je za dani graf ▫$\chi_c \ge 2$▫ je NP-poln.
    Vir: Preprint series. - ISSN 1318-4865 (Vol. 40, št. 820, 2002, str. 1-15)
    Vrsta gradiva - članek, sestavni del
    Leto - 2002
    Jezik - angleški
    COBISS.SI-ID - 11627865

    Povezava(-e):

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

vir: Preprint series. - ISSN 1318-4865 (Vol. 40, št. 820, 2002, str. 1-15)
loading ...
loading ...
loading ...

Vnos na polico