VSE knjižnice (vzajemna bibliografsko-kataložna baza podatkov COBIB.SI)
  • On vertex-parity edge-colorings
    Lužar, Borut ; Petruševski, Mirko ; Škrekovski, Riste
    ǂA ǂvertex signature ▫$\pi$▫ of a finite graph ▫$G$▫ is any mapping ▫$\pi \, : \, V(G)\to \{0,1\}$▫. An edge-coloring of ▫$G$▫ is said to be \textit{vertex-parity} for the pair ▫$(G,\pi)$▫ if for ... every vertex ▫$v$▫ each color used on the edges incident to ▫$v$▫ appears in parity accordance with ▫$\pi$▫, i.e. an even or odd number of times depending on whether ▫$\pi(v)$▫ equals ▫$0$▫ or ▫$1$▫, respectively. The minimum number of colors for which ▫$(G,\pi)$▫ admits such an edge-coloring is denoted by ▫$\chi'_p(G,\pi)$▫. We characterize the existence and prove that ▫$\chi'_p(G,\pi)$▫ is at most ▫$6$▫. Furthermore, we give a structural characterization of the pairs ▫$(G,\pi)$▫ for which ▫$\chi'_p(G,\pi)=5$▫ and ▫$\chi'_p(G,\pi)=6$▫. In the last part of the paper, we consider a weaker version of the coloring, where it suffices that at every vertex, at least one color appears in parity accordance with ▫$\pi$▫. We show that the corresponding chromatic index is at most ▫$3$▫ and give a complete characterization for it.
    Vir: Journal of combinatorial optimization. - ISSN 1382-6905 (Vol. 35, iss. 2, 2018, str. 373-388)
    Vrsta gradiva - članek, sestavni del
    Leto - 2018
    Jezik - angleški
    COBISS.SI-ID - 2048470291
    DOI

Vnos na polico