DIKUL - logo
(UL)
  • Odd edge coloring of graphs
    Lužar, Borut ; Petruševski, Mirko ; Škrekovski, Riste
    Barvanje povezav grafa ▫$G$▫ je liho barvanje povezav, če za vsako vozlišče ▫$v$▫ grafa ▫$G$▫ in za vsako barvo ▫$c$▫, vozlišče ▫$v$▫ uporabi barvo ▫$c$▫ lihokrat ali pa je sploh ne uporabi. V [L. ... Pyber, Covering the edges of a graph by..., Graphs and Numbers, Colloq. Math. Soc. János Bolyai 60 (1991), 583-610.] je Pyber dokazal, da 4 barve zadoščajo za liho povezavno barvanje vsakega enostavnega grafa. Nedavno so bili nekateri rezultati o tem tipu barvanj (multi)grafov uspešno uporabljeni pri reševanju problema parnosti lic povezavnega barvanja [B. Lužar and R. Škrekovski, Improved bound on facial parity edge coloring, Discrete Math. 313 (2013), 2218-2222 in J. Czap, S. Jendrol', F. Kardoš and R. Soták, Facial parity edge colouring of plane pseudographs, Disc. Math. 312 (2012), 2735-2740]. V tem članku predstavimo dodatne rezultate, in sicer dokažemo, da 6 barv zadošča za liho povezavno barvanje vsakega povezanega (multi)grafa brez zank, navedemo primere, ko je ta zgornja meja dosežena, in karakteriziramo družino povezanih (multi)grafov brez zank, pri katerih je meja 6 dosežena. Predstavimo tudi nekaj odprtih problemov.
    Vir: Ars mathematica contemporanea. - ISSN 1855-3966 (Vol. 9, no. 2, 2015, str. 267-277)
    Vrsta gradiva - članek, sestavni del ; neleposlovje za odrasle
    Leto - 2015
    Jezik - angleški
    COBISS.SI-ID - 2048342547

    Povezava(-e):

    http://amc-journal.eu/index.php/amc/article/download/576/736
    Digitalna knjižnica Slovenije - dLib.si

vir: Ars mathematica contemporanea. - ISSN 1855-3966 (Vol. 9, no. 2, 2015, str. 267-277)

loading ...
loading ...
loading ...

Vnos na polico