On vertex-parity edge-colorings

A vertex signature $$\pi $$ π of a finite graph G is any mapping $$\pi \,{:}\,V(G)\rightarrow \{0,1\}$$ π : V ( G ) → { 0 , 1 } . An edge-coloring of G is said to be vertex-parity for the pair $$(G,\pi )$$ ( G , π ) 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)$$ π ( v ) equals 0 or 1, respectively. The minimum number of colors for which $$(G,\pi )$$ ( G , π ) admits such an edge-coloring is denoted by $$\chi '_p(G,\pi )$$ χ p ′ ( G , π ) . We characterize the existence and prove that $$\chi '_p(G,\pi )$$ χ p ′ ( G , π ) is at most 6. Furthermore, we give a structural characterization of the pairs $$(G,\pi )$$ ( G , π ) for which $$\chi '_p(G,\pi )=5$$ χ p ′ ( G , π ) = 5 and $$\chi '_p(G,\pi )=6$$ χ p ′ ( G , π ) = 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.