WEAK-ODD EDGE-COLORING OF DIGRAPHS

Abstract

A weak-odd edge-coloring of a digraph \(D\) is a (not necessarily proper) edge-coloring such that for each vertex \(v \in V(D)\) at least one color \(c\) satisfies the following requirement: if \(d^+(v)>0\) then \(c\) appears an odd number of times on the outgoing edges at \(v\); and if \(d^-(v)>0\) then \(c\) appears an odd number of times on the ingoing edges at \(v\). The minimum number of colors sufficient for a weak-odd edge-coloring of \(D\) is the weak-odd chromatic index, denoted \(\chi'_{wo}(D)\).

In this article we prove that \(\chi'_{wo}(D)\leq 3\) for every digraph \(D\), and show that this bound is sharp. We study when does a graph admit an orientation so that the obtained digraph is weak-odd 1-edge-colorable. We also prove that every graph admits an orientation for which the obtained digraph is weak-odd 2-edge-colorable.