VSE knjižnice (vzajemna bibliografsko-kataložna baza podatkov COBIB.SI)
  • Degenerate and star colorings of graphs on surfaces
    Mohar, Bojan, 1956- ; Špacapan, Simon
    V članku so podane zgornje meje za degenerirano in zvezdno kromatično število in za njuno skupno posplošitev v odvisnosti od roda grafov. Kot pomožno orodje je dokazana naslednja posplošitev ... rezultata, ki ga je dokazal Fertin s soavtorji za zvezdno kromatično število. Če je ▫$G$▫ graf z maksimalno stopnjo ▫$\Delta$▫, potem ima ▫$G$▫ degenerirano zvezdno barvanje z ▫$O(\Delta^{3/2})$▫ barvami. Ta rezultat je uporabljen v dokazu glavnega izreka, ki pravi, da ima vsak graf roda ▫$g$▫ degenerirano zvezdno barvanje z ▫$O(g^{3/5})$▫ barvami. Dodani so primeri, ki dokazujajo, da so dobljene ocene optimalne do logaritemskega faktorja.
    Vir: Topological and geometric graph theory (Str. 340-349)
    Vrsta gradiva - prispevek na konferenci
    Leto - 2012
    Jezik - angleški
    COBISS.SI-ID - 16199769

    Povezava(-e):

    http://dx.doi.org/10.1016/j.ejc.2011.09.007

Vnos na polico