VSE knjižnice (vzajemna bibliografsko-kataložna baza podatkov COBIB.SI)
  • Linear colouring of planar graphs with prescribed girth and maximum degree [Elektronski vir]
    Erman, Rok ; Škrekovski, Riste
    A linear colouring of a graph is a proper vertex colouring such that the subgraph induced by any two colour classes is a set of vertex disjoint paths. The corresponding linear chromatic number of a ... graph ▫$G$▫, namely ▫$\mathrm{lc}(G)$▫, is the minimum number of colours in a linear colouring of ▫$G$▫. We prove that for a graph ▫$G$▫ with girth ▫$g \geq 8$▫ and maximum degree ▫$\Delta \geq 7$▫ the inequality on its linear colouring number holds: ▫$\mathrm{lc}(G) \leq \lceil \frac{\Delta}{2}\rceil +1$▫. This improves the girth assumption of a previously known bound of Raspaud and Wang.
    Vir: Preprint series [Elektronski vir]. - ISSN 2232-2094 (Vol. 49, št. 1142, 2011, str. 1-10)
    Vrsta gradiva - e-članek
    Leto - 2011
    Jezik - angleški
    COBISS.SI-ID - 15841113

    Povezava(-e):

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

Vnos na polico