Notes on weak-odd edge colorings of digraphs

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

Ars mathematica contemporanea, Volume 22 (2022) no. 2, article no. 05, 21 p.

Abstract

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.

Article information

DOI: 10.26493/1855-3974.1955.1cd

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