On vertex-parity edge-colorings
type: Item
instance of: scholarly article
title: On vertex-parity edge-colorings
zbMATH Open document ID: 1401.05123
author: Borut Lužar
author: Mirko Petruševski
author: Riste Škrekovski
published in: Journal of Combinatorial Optimization
publication date: 2018-03-01T00:00:00Z
review text: For a finite general graph (where parallel edges and loops are allowed), a signature is a map \(\pi : V(G) \rightarrow \{0,1\}\). For a given edge coloring (not necessarily proper) of \(G\), let \(G_c\) be the subgraph of \(G\) induced by the edges of color \(c\). For a given signature \(\pi\), a vertex parity of the pair \((G,\pi)\) is an edge coloring of \(G\) such that for every vertex \(u\in V(G)\) and every color \(c\) we have \(d_{G_c}(u)\equiv \pi(u)\pmod{2}\). The pair \((G,\pi)\) is proper if (i) every vertex \(u\) with \(\pi(u) = 0\) has an even degree \(d_G(u)\) and (ii) every component with a unique vertex with \(\pi\)-value of one has no edges (i.e.~consists of an isolated vertex.) The minimum number of colors for which \((G,\pi)\) has a vertex parity is denoted by \(\chi_p^\prime(G,\pi)\). The main result in this paper is to characterize the existence of the vertex parity and to prove that \(\chi_p^\prime(G,\pi)\leq 6\) for every proper pair \((G,\pi)\). The proper pairs \((G,\pi)\) where \(G\) is connected and \(\chi_p^\prime(G,\pi)\leq 5\) are also characterized. In the last part of the paper, edge colorings of \((G,\pi)\) satisfying a weaker condition, namely that for every vertex \(u\in V(G)\) and at least one color \(c\) we have \(d_{G_c}(u)\equiv \pi(u)\pmod{2}\), are completely characterized and it is shown that the corresponding chromatic index of \((G,\pi)\) is at most \(3\).
reviewed by: Geir Agnarsson
Mathematics Subject Classification ID: 05C15
zbMATH DE Number: 6845570
zbMATH Keywords: vertex-parity edge-coloring
zbMATH Keywords: vertex-parity chromatic index
zbMATH Keywords: weak vertex-parity edge-coloring
zbMATH Keywords: vertex signature
MaRDI profile type: Publication
full work available at URL: s10878-017-0178-1
OpenAlex ID: W2756592572
cites work: Factors and factorizations of graphs. Proof techniques in factor theory
cites work: Odd edge-colorability of subcubic graphs
cites work: Q5422499
cites work: Q3097395
cites work: Facial parity edge colouring of plane pseudographs
cites work: Flows and generalized coloring theorems in graphs
cites work: Odd edge coloring of graphs
cites work: Improved bound on facial parity edge coloring
cites work: On the structure of factorizable graphs. II
cites work: A note on weak odd edge-colorings of graphs
cites work: Odd 4‐edge‐colorability of graphs
cites work: Q3137210
cites work: Combinatorial optimization. Polyhedra and efficiency (3 volumes)
cites work: Flows and parity subgraphs of graphs with large odd-edge-connectivity
cites work: Polyhedral decompositions of cubic graphs
cites work: Graph Factors and Matching Extensions
DOI: 10.1007/S10878-017-0178-1
description: scientific article; zbMATH DE number 6845570