It seems to me that such colorings are tightly closely related to 2-factorizations of graphs. Indeed every color class represents a subgraph which is a disjoint union of directed paths and cycles. Let's denote by $C(x)$ the set of edges colored $x$. x\in G$. We can see that the underlying graphs of$C(x)$and$C(-x)$coincide, but they have opposite orientation. When$2x\neq 0$then the underlying subgraph must have maximum degree 2. When$2x=0$then$C(x)$is a matching. It's possible to show that a graph with$n$vertices and maximum degree$\Delta$can be written as a union of at most$\lfloor \frac{\Delta+1}{2}\rfloor$subgraphs of maximum degree 2. Each of these subgraphs is a union of paths and cycles, so we can assign two colors to the corresponding directed edges. This shows that there is always a coloring satisfying the properties in the question coming from$\mathbb Z/(\Delta+1)\mathbb Z$. This would be the most straightforward analog of Vizing's theorem, and . Notice that$\Delta+1$cannot be improved. 1 I will expand on my comment. It seems to me that such colorings are tightly related to 2-factorizations of graphs. Indeed every color class represents a subgraph which is a disjoint union of directed paths and cycles. Let's denote by$C(x)$the set of edges colored$x$. We can see that the underlying graphs of$C(x)$and$C(-x)$coincide, but they have opposite orientation. It's possible to show that a graph with$n$vertices and maximum degree$\Delta$can be written as a union of at most$\lfloor \frac{\Delta+1}{2}\rfloor$subgraphs of maximum degree 2. Each of these subgraphs is a union of paths and cycles, so we can assign two colors to the corresponding directed edges. This shows that there is always a coloring satisfying the properties in the question coming from$\mathbb Z/(\Delta+1)\mathbb Z$. This would be the most straightforward analog of Vizing's theorem, and$\Delta+1\$ cannot be improved.