Notes on weak-odd edge colorings of digraphs

César Hernández-Cruz, Mirko Petruševski, Riste Škrekovski


A weak-odd edge coloring of a general digraph D is a (not necessarily proper) coloring of its edges such that for each vertex v ∈ V(D) at least one color c satisfies the following conditions: if dD(v) > 0 then c appears an odd number of times on the incoming edges at v; and if dD+(v) > 0 then c appears an odd number of times on the outgoing edges at v. The minimum number of colors sufficient for a weak-odd edge coloring of D is the weak-odd chromatic index, denoted χwo(D). It is known that χwo(D) ≤ 3 for every digraph D, and that the bound is sharp. In this article we show that the weak-odd chromatic index can be determined in polynomial time. Restricting to edge colorings of D with at most two colors, the minimum number of vertices v ∈ V(D) for which no color c satisfies the above conditions is the defect of D, denoted def(D). Surprisingly, it turns out that the problem of determining the defect of digraphs is (polynomially) equivalent to the problem of finding the matching number of simple graphs. Moreover, we characterize the classes of associated digraphs and tournaments in terms of the weak-odd chromatic index and the defect.


Digraph, weak-odd edge coloring, weak-odd chromatic index, defective coloring, tournament

Full Text:



ISSN: 1855-3974

Issues from Vol 6, No 1 onward are partially supported by the Slovenian Research Agency from the Call for co-financing of scientific periodical publications