On vertex-parity edge-colorings (Q1702821)

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\).