ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 22 (2022) #P2.05 / 249–269
https://doi.org/10.26493/1855-3974.1955.1cd
(Also available at http://amc-journal.eu)
Notes on weak-odd edge colorings of digraphs*
César Hernández-Cruz
Facultad de Ciencias, Universidad Nacional Autónoma de México,
Av. Universidad 3000, Circuito Exterior S/N, Ciudad Universitaria, CDMX, México
Mirko Petruševski †
Faculty of Mechanical Engineering - Skopje, University Ss Cyril and Methodius,
1000 Skopje, Macedonia
Riste Škrekovski
FMF, University of Ljubljana, 1000 Ljubljana, Slovenia, and
Faculty of Information Studies, 8000 Novo mesto, Slovenia, and
University of Primorska, FAMNIT, 6000 Koper, Slovenia
Received 18 March 2019, accepted 29 July 2021, published online 27 May 2022
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 d−D(v) > 0 then c appears an odd number of times on the incoming edges at
v; and if d+D(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.
Keywords: Digraph, weak-odd edge coloring, weak-odd chromatic index, defective coloring, tourna-
ment.
Math. Subj. Class. (2020): 05C15, 05C20
*This work is partially supported by ARRS Program P1-0383 and ARRS Project J1-1692.
†Corresponding author.
E-mail addresses: japo@ciencias.unam.mx (César Hernández-Cruz), mirko.petrushevski@gmail.com
(Mirko Petruševski), skrekovski@gmail.com (Riste Škrekovski)
cb This work is licensed under https://creativecommons.org/licenses/by/4.0/
250 Ars Math. Contemp. 22 (2022) #P2.05 / 249–269
1 Introduction
Throughout the article we mainly follow terminology and notation used in [1]. All graphs
and digraphs are considered to be finite. Loops, parallel edges and parallel arcs are admis-
sible, i.e., strictly speaking, we consider the general setup of pseudographs and directed
pseudographs, but in order to avoid lengthy terminology, we abbreviate these terms to
‘graphs’ and ‘digraphs’, respectively.
Cheilaris et al. [4] introduced the notion of odd coloring of a hypergraphH as a vertex
coloring such that for every (hyper-)edge e ∈ E(H) there is a color c with an odd number
of vertices of e colored by c. Restricting to graphs G (and thus to plain edges), the previous
coloring notion is merely the usual notion of ‘proper’ coloring of G. Through interchanging
the roles played by vertices and edges, initially motivated by [5, 6], the analogous edge
coloring notion for graphs was introduced in [10] as follows. An edge coloring of G is said
to be weak-odd if it holds that:
(WO) For every vertex v ∈ V (G) with degree dG(v) > 0, at least one color c appears an
odd number of times on the set of edges incident with v.
The additional adjective ‘weak’ has been included in the name simply in order to dif-
ferentiate this from the related, already existing, notion of ‘odd edge coloring’ of graphs,
defined in [12]. (The latter notion has stronger requirements for the colors appearing at a
vertex.)
Let us clarify that, by definition, any loop at v colored by c contributes 2 to the count of
appearances of c on EG(v) (the set of all edges incident with v). An obvious necessary and
sufficient condition for weak-odd edge colorability of graph G is the absence of ‘isolated
loops’, i.e., nonempty trivial components. A weak-odd edge coloring of G using at most
k colors is referred to as a weak-odd k-edge coloring of G, and such a graph is said to be
weak-odd k-edge colorable. The weak-odd chromatic index, χ′wo(G), is the minimum k for
which G is weak-odd k-edge colorable. Obviously, apart from ‘isolated loops’, any other
loop addition or removal does not influence the existence nor alters the value of χ′wo(G).
The following characterization of graphs G in terms of χ′wo(G) was obtained in [10]. It
makes use of the next two notions. A graph G is even (resp. odd) if every vertex v ∈ V (G)
has even (resp. odd) degree dG(x).
Theorem 1.1. For any connected graph G whose edge set does not consist entirely of
loops, it holds that
χ′wo(G) =
⎧⎪⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎪⎩
0 if G =K1,
1 if G is odd,
2 if G has even order or is not even,
3 if G is even, has odd order, and is not K1.
This paper treats the analogous coloring notion for digraphs. In the next section we fur-
ther explain the motivation behind the definition of ‘weak-odd edge coloring’ of digraphs,
introduced in [11], and then show that the corresponding coloring index χ′wo can be deter-
mined in linear time. We also address a related problem concerning the minimum number
of vertices at which an arbitrary 2-edge coloring of a digraph fails at being ‘weak-odd’,
and prove a connection with the problem of determining the matching number of a simple
graph. In Section 3, the discussion restricts to two common classes of digraphs, namely,
C. Hernández-Cruz et al.: Notes on weak-odd edge colorings of digraphs 251
the class of associated digraphs1 and the class of tournaments. For each of these classes we
give a descriptive characterization of their members in terms of χ′wo. In the final section
we briefly convey our thoughts on possible further work on the topic of weak-odd edge
colorings of digraphs. For the end of this introductory section, we mention some common
notions and facts that will be frequently used throughout.
1.1 General terminology and notation
We denote the symmetric difference of sets A,B by A ⊕ B. The same notation is in use
for the symmetric difference of two spanning subgraphs A,B of a ground graph. Given a
graph G and an even-sized subset T of V (G), a spanning subgraph H is a T -join of G if
dH(v), the degree of v with respect to H , is odd for all v ∈ T and even for all v ∈ V (G)∖T .
The symmetric difference of a T ′-join and a T ′′-join of G is a T ′ ⊕ T ′′-join, which yields
the following classical result (see [14]): every connected graph G contains a T -join. In
particular, every even-ordered connected graph G has an odd factor (i.e., a V (G)-join).
An edge coloring of a graph G (resp. digraph D) with color set S is an assignment
E(G) → S (resp. A(D) → S). Every T -join of G can be interpreted as an edge coloring
with color set {1,2} such that 1 is used an odd number of times at each v ∈ T and and even
number of times (possibly zero) at each v ∈ V (G) ∖ T .
Given a digraph D and a vertex v ∈ V (D), the size of the set ∂−D(v), of incoming
edges at v, (resp. ∂+D(v), of outgoing edges at v,) is the in-degree d−D(v) (resp. out-degree
d+D(v)) of the vertex v; we call each of ∂−D(v) and ∂+D(v) (resp. d−D(v) and d+D(v)) a semi-
cut (resp. semi-degree) of v. Since loops are allowed, let us clarify that ∂−D(v) ∩ ∂+D(v)
constitutes the set of loops at v; in other words, any loop at vertex v contributes 1 to each
semi-degree of v, i.e., strictly speaking d−D(v) and d−D(v) are the semi-pseudodegrees of
v (the in-pseudodegree and out-pseudodegree, respectively). The sum dD(v) = d−D(v) +
d+D(v) is the degree of v; a vertex of degree 0 is said to be isolated. Given a nonisolated
vertex v, if d−D(v) = 0 (resp. d+D(v) = 0), then v is a source (resp. sink) of D. Any source
or sink is a peripheral vertex of D, whereas a nonisolated vertex that is neither a source
nor a sink is an intermediate vertex. A vertex u is said to dominate a vertex v if v ∈ ∂+D(u);
equivalently, v is dominated by u.
Two graphs or digraphs are considered identical if they are isomorphic to each other.
The numbers of vertices and edges of graph or digraph D are denoted by n(D) and m(D);
these basic parameters are the order and size of D, respectively; a graph or digraph of order
1 (resp. size 0) is trivial (resp. empty).
A graph is bipartite if its vertex set can be partitioned into two subsets X and Y so
that every edge has one end in X and one end in Y ; such a partition (X,Y ) is called a
bipartition of the graph, and X and Y its partite sets. We denote a bipartite graph G with
bipartition (X,Y ) by G[X,Y ]. Given a digraph D, its split (or bipartite representation),
BG(D), is the bipartite graph G whose partite sets V +, V − are copies of V (D). For each
v ∈ V (D), there is one vertex v+ ∈ V + and one v− ∈ V −. For each directed uv-edge in
D, there is an edge with endpoints u+ and v− in G. Hence, the degrees of the vertices
v+, v− in the split of D are precisely the out-degree and in-degree of v in D, respectively;
the pair (v+, v−) is obtained by splitting v in regard to D. The re-identification of each
such pair (v+, v−) into v results in the so-called underlying graph of D, denoted G(D).
1A digraph D is associated if for every arc (u, v) of D, the arc (v, u) is also present in D, and the number
of loops at any vertex is even.
252 Ars Math. Contemp. 22 (2022) #P2.05 / 249–269
Furthermore, any balanced bipartite graph G is a split of some digraph D, i.e., can be
‘transformed’ into D by reversing the described procedure.
The other way around, any graph G can be regarded as a digraph D(G), by replacing
each of its edges by two oppositely oriented arcs with the same ends (each loop of G gives
rise to two directed loops on the same vertex); this digraph is the associated digraph of G.
One may also obtain a digraph D from a graph G by replacing each edge by one arc on the
same endpoints; such a digraph D is an orientation of G. A tournament is an orientation
of a complete graph. Conversely, the underlying graph G(D) of a digraph D is obtained
by ‘forgetting orientation’. A directed path or directed cycle is an orientation of a path or
cycle in which each vertex dominates its successor in the sequence.
A digraph D is said to be strongly connected (or simply strong) if for any pair u, v
of its vertices there is a directed uv-path, i.e., a directed path joining vertex u with vertex
v. Given a digraph D, every maximal strong subdigraph of D is a strong component of
D. The condensation C(D) of a digraph D is the loopless directed (multi)graph whose
vertices correspond to the strong components of D, with any two vertices of C(D) being
linked by as many directed edges as there are directed edges in D linking the corresponding
strong components, and with the consistent orientation. The peripheral strong components
of D which correspond to the vertices of C(D) that are sources (resp. sinks), are the ini-
tial (resp. terminal) strong components; the remaining strong components of D are called
intermediate or isolated according to the nature of the corresponding vertices in C(D).
2 Weak-odd edge colorings of digraphs
In the realm of digraphs D, when defining the notion of ‘weak-odd edge coloring’ two
options come to mind. Initially, one may obtain a ‘directed version’ of the condition (WO)
as follows:
(
Ð→
W
Ð→
O) For every vertex v ∈ V (D), on each nonempty semi-cut of v at least one color c
appears an odd number of times.
However, the above ‘definition’ fails to capture the essence of digraphs since it basically
ignores the fact that arc sets ∂−D(v) and ∂+D(v) are incident with a common vertex (namely,
v). Actually, a moment’s thought reveals that, if we decide to adopt the initial definition,
then this coloring notion for digraphs would be merely a ‘disguise’ of weak-odd edge
coloring of bipartite graphs with equally sized partite sets. Namely, it can readily be seen
that an edge coloring of D satisfies condition (
Ð→
W
Ð→
O) if and only if the induced edge coloring
on BG(D) satisfies condition (WO). Consequently, in view of Theorem 1.1, every digraph
D admits a 3-edge coloring obeying (
Ð→
W
Ð→
O); moreover, three colors are indeed required if
and only if at least one component of BG(D) is a nonempty even graph of odd order. One
such example is depicted in Figure 1. Notice that if at least one of the loops is removed
from D then the obtained digraph would admit a 2-edge coloring that satisfies condition
(
Ð→
W
Ð→
O).
As noticed, unlike for graphs, in the realm of digraphs the presence of loops may in-
fluence the value of the corresponding chromatic index in a nontrivial manner. This is so
because any such loop in the digraph is no longer a loop in its split.
A more appropriate definition of the notion of ‘weak-odd edge coloring’ for digraphs,
the one we shall adopt in this study, is obtained as follows. Recall that any graph G can
be seen as a digraph, the associated digraph D(G). In the obvious fashion, every edge
C. Hernández-Cruz et al.: Notes on weak-odd edge colorings of digraphs 253
u
v
w w+ w−
v+ v−
u+ u−
Figure 1: (left) A digraph D that fails condition (
Ð→
W
Ð→
O) under any 2-edge coloring, and
(right) its split BG(D) with the left-hand (resp. right-hand) partite set representing V +
(resp. V −). The nonempty component of BG(D) is an even graph of odd order.
u u
v v
w w
Figure 2: Digraphs D1 (left) and D2 (right) are obtained from the digraph in Figure 1 by
removing a certain loop (at v and at u, respectively). Both admit 2-edge colorings fulfilling
condition (
Ð→
W
Ð→
O), but none admits a 2-edge coloring satisfying (
ÐÐ→
WO).
coloring φ of G can be interpreted as an edge coloring φD of D(G). Notice that if φ is
weak-odd then φD satisfies the condition (
ÐÐ→
WO) below, which states a stronger requirement
than the one imposed by (
Ð→
W
Ð→
O). This particular reasoning served as the motivation in [11]
for defining an edge coloring of a digraph D to be weak-odd if:
(
ÐÐ→
WO) For every vertex v ∈ V (D), at least one color c appears an odd number of times
on each nonempty semi-cut of v.
Same as with (
Ð→
W
Ð→
O), in case v is a sink (resp. source), the condition (
ÐÐ→
WO) amounts to
the appearance of c an odd number of times on the incut ∂−D(v) (resp. outcut ∂+D(v)). The
difference between (
Ð→
W
Ð→
O) and (
ÐÐ→
WO) is reflected at the intermediate vertices (cf. Figure 2).
The minimum number of colors sufficient for a weak-odd edge coloring of a digraph D
is the weak-odd chromatic index, denoted χ′wo(D). A weak-odd edge coloring of D using
at most k colors is referred to as a weak-odd k-edge coloring, and any such D is said to be
weak-odd k-edge colorable. Hence, χ′wo(D) is the minimum k for which D is weak-odd
k-edge colorable.
254 Ars Math. Contemp. 22 (2022) #P2.05 / 249–269
Interestingly, analogous to graphs, the same upper bound (of three colors) holds for the
weak-odd chromatic index of digraphs. Namely, the following was proven in [11].
Theorem 2.1. Every digraph is weak-odd 3-edge colorable.
As already illustrated through Figures 1 and 2, the bound χ′wo(D) ≤ 3 is sharp, i.e.,
not every digraph is weak-odd 2-edge colorable. Analogous to the setting of graphs, it is
quite trivial to characterize which digraphs are weak-odd 1-edge colorable. Indeed, the
inequality χ′wo(D) ≤ 1 holds if and only if for every vertex v ∈ V (D) both semi-degrees
d−D(v), d+D(v) are odd or zero. Furthermore, χ′wo(D) = 0 holds precisely when D is empty.
Thus, in order to characterize all digraphs in terms of their weak-odd chromatic index, it
suffices to figure out which are the weak-odd 2-edge colorable ones.
2.1 Characterization of weak-odd 2-edge colorability
The partial split, PS(D), of given digraph D is a graph obtained by splitting (in regard
to D) only those vertices v ∈ V (D) for which at least one semi-degree is even (including
zero), and then forgetting orientation. In other words, PS(D) is the graph obtained from
BG(D) by re-identifying each pair (u+, u−) for which both d+D(u) and d−D(u) are odd
(cf. Figure 3). In particular, if no vertex of D has only odd-sized semi-cuts, then PS(D)
is the same graph as the split BG(D); contrarily, if every nonisolated vertex of D has only
odd-sized semi-cuts, then PS(D) is the same as the underlying graph G(D). However, in
general, these three graphs related to D differ from each other.
D1 : D2 :
u+ u−
v+ v−
w+ w− w+ w
−
v
u+ u− u+ u− u
v+ v
−
w+ w−
v+ v
−
w+ w
−
Figure 3: The split BG(D1) and partial split PS(D1) (left), and the split BG(D2) and
partial split PS(D2) (right), where D1,D2 are the digraphs from Figure 2. The induced
3-partition {V1, V2, V3} of V (PS(D1)) consists of V1 = {v}, V2 = {u+, u−,w+,w−}
and V3 = ∅, whereas the corresponding 3-partition of V (PS(D2)) has V1 = {u},
V2 = {v+, v−,w+,w−}, V3 = ∅.
We distinguish between three types of vertices in PS(D) inducing a 3-partition
{V1, V2, V3} of V (PS(D)):
• the first type of vertices, constituting V1, are the members of V (D) ∩ V (PS(D)),
i.e., the vertices u of D having odd semi-degrees d+D(u), d−D(u).
• the second type of vertices, forming V2, are the members v of V (PS(D))/V (D)
that have even degree dPS(D)(v).
• finally, the third type of vertices, comprising V3, are the members w of V (PS(D))/
V (D) that have odd degree dPS(D)(w).
C. Hernández-Cruz et al.: Notes on weak-odd edge colorings of digraphs 255
For simplicity of presentation, on several occasions we shall employ the following ad-
hoc terminology and notation. Given a graph G, a vertex x ∈ V (G) is said to be even
(resp. odd) if dG(x) is even (resp. odd). The set of even (resp. odd) vertices of G is denoted
EvenV (G) (resp. OddV (G)). Note that, by the handshake lemma, OddV (G) is always
even-sized. Thus, V3 above equals OddV (PS(D)), whereas V1 ⊍ V2 = EvenV (PS(D)).
Theorem 2.2. A digraph D is weak-odd 2-edge colorable if and only if for every nonempty
component K of PS(D) we have that V (K) ∩ V2 is even-sized or V (K) ∩ V3 ≠ ∅.
Proof. Assuming χ′wo(D) ≤ 2, let φ ∶ A(D) → {1,2} be a weak-odd edge coloring of D
and consider the induced edge coloring of PS(D). Observe that for every vertex u ∈ V1,
each of the colors 1 and 2 is used an even number of times on EPS(D)(u). Indeed, the edge
set EPS(D)(u) corresponds to the entire cut ∂D(u) = ∂+D(u) ⊍ ∂−D(u); thus, since both
constituents in this disjoint union are odd-sized, for every color c ∈ {1,2} the parities of
∣∂+D(u)∩φ−1(c)∣ and ∣∂−D(u)∩φ−1(c)∣ are equal. In contrast, for every nonisolated vertex
v ∈ V2, each of the colors 1 and 2 appears an odd number of times on EPS(D)(v). The
reason behind this is that the edge set EPS(D)(v) corresponds to a nonempty even-sized
semi-cut of a vertex in D.
Therefore, if K is a nonempty component of PS(D) such that V (K) ⊆ V1 ⊍ V2,
then each of the two color classes induces in K a subgraph Ki (i ∈ {1,2}) such that
OddV (Ki) = V (K) ∩ V2. Consequently, the intersection V (K) ∩ V2 is even-sized.
Arguing in the opposite direction, assume now that every nonempty component K of
PS(D) meets the stated requirements. We construct an assignment E(K) → {1,2} as
follows. If V (K) ∩ V2 is even-sized, then define T = V (K) ∩ V2. Otherwise, select an
odd-sized subset SK ⊆ V (K) ∩ V3 and define T = (V (K) ∩ V2) ⊍ SK . Either way, T
is an even-sized subset of V (K). Therefore, there exists a T -join H of K. Color E(H)
with 1 and E(K)/E(H) with 2. Consider the induced edge coloring of D, and observe
the following.
(1) At each vertex u ∈ V (D) ∩ V1, precisely one of the colors 1,2 satisfies condition
(
ÐÐ→
WO). Indeed, by construction, each color is used an even number of times on
∂D(u), and thus has equal parities of appearance on the odd-sized sets ∂−D(u) and
∂+D(u), respectively.
(2) At each nonisolated vertex v ∈ V (D)/V1 such that the vertices v+, v− ∈ V2, colors 1
and 2 both satisfy condition (
ÐÐ→
WO). Namely, by construction, color 1 is used an odd
number of times on each nonempty semi-cut of v; on the other hand, both ∂−D(v) and
∂+D(v) are even-sized.
(3) At each vertex w ∈ V (D)/V1 such that one of the vertices w+,w− belongs in V2 (and
the other in V3), precisely one of the colors 1,2 satisfies condition (
ÐÐ→
WO). Indeed,
if the ‘half’ of w belonging to V3 is used in some SK then color 1 meets (
ÐÐ→
WO);
otherwise, color 2 does so.
Thus, the digraph D is weak-odd 2-edge colorable.
For example, the digraph D depicted in Figure 4 is weak-odd 2-edge colorable because
the only nonempty component of PS(D) intersects V3. With the notation employed in the
256 Ars Math. Contemp. 22 (2022) #P2.05 / 249–269
proof, if we take E(H) to consist of x+y−, y+u, and a uz− edge, then the induced weak-
odd 2-edge coloring of D assigns color 1 to xy, yu and a uz arc, and assigns color 2 to the
rest of A(D).
x
yz
u
x+ x−
y+ y−
z+ z−
u
Figure 4: A digraph D (left) and its partial split PS(D) (right). The induced 3-partition
has V1 = {u}, V2 = {x+, x−, y−, z−} and V3 = {y+, z+}.
Contrarily, the digraph D depicted in Figure 5 is not weak-odd 2-edge colorable, since
the induced 3-partition has V1 = {u}, V2 = {x+, x−, y+, y−, z+, z−} and V3 = ∅, the only
nonempty component of its partial split does not intersect V3 and contains an odd number
of vertices from V2.
x
yz
u
x+ x−
y+ y−
z+ z−
u
Figure 5: A digraph D (left) and its partial split PS(D) (right).
The proof of Theorem 2.2 and the fact that the problem of constructing a T -join of
any connected graph G for a given even-sized subset T of V (G) is solvable in linear time
(see [14]), imply that the decision problem of whether χ′wo(D) ≤ 2 is solvable in linear
time; in the affirmative case, a weak-odd 2-edge coloring of D can be found in linear time.
Thus, in view of Theorem 2.1 and the subsequent discussion, we conclude the following.
Corollary 2.3. The weak-odd chromatic index of any digraph D and a corresponding
weak-odd χ′wo(D)-edge coloring can be determined in linear time.
To end this subsection we point out an infinite family of digraphs having weak-odd
chromatic index equal to 3. A digraph is said to be even if every vertex v ∈ V (D) is of
C. Hernández-Cruz et al.: Notes on weak-odd edge colorings of digraphs 257
even degree dD(v); in other words, the requirement is that the semi-degrees of v are of
equal parity.
Figure 6: Two even digraphs with weak-odd chromatic index 3.
Proposition 2.4. If an even digraph D has an odd number of peripheral vertices, then
χ′wo(D) = 3.
Proof. We may assume that D is connected. Consider the partial split PS(D) of D and the
induced 3-partition {V1, V2, V3}. Obviously, V3 = ∅ and the number of isolated vertices
of PS(D) equals the number of peripheral vertices of D. However, this implies that the
number of nonisolated vertices of PS(D) which belong in V2 is odd. Therefore, an odd
number of nonempty components of PS(D) fail to meet the requirements of Theorem 2.2.
Notice that out of the two even digraphs depicted in Figure 6, only the left one has an
odd number of peripheral vertices; nevertheless, neither is weak-odd 2-edge colorable. This
demonstrates that the condition ‘an odd number of peripheral vertices’ from the statement
of Proposition 2.4, although sufficient, is by no means necessary.
2.2 Defective weak-odd 2-edge colorings
The following straightforward result serves as our motivation for the brief discussion within
this subsection. In a way, it tells that every graph can be almost weak-odd 2-edge colored.
Proposition 2.5. Every connected graph G admits a 2-edge coloring such that condition
(WO) is satisfied at each vertex apart from a prescribed vertex v ∈ V (G).
Proof. We construct an even-sized subset T of V (G) as follows. If n(G) is even, then
define T = V (G); otherwise, let T = V (G)/{v}. Since G is connected, consider a T -join
H of G. Color E(H) with 1, and the rest of E(G) with 2. The obtained 2-edge coloring
of G clearly fulfills condition (WO) at each vertex differing from v.
One naturally wonders if there exists an analogous result for digraphs that bounds (pre-
sumably with 1) the number of ‘defective vertices’, in regard to condition (
ÐÐ→
WO), for some
2-edge coloring? Unfortunately, in contrast to graphs, there are connected digraphs such
that for any 2-edge coloring the condition (
ÐÐ→
WO) fails at an unbounded number of vertices.
To construct examples, consider as a ‘gadget digraph’ D the right-hand digraph from
Figure 6. Observe that no 2-edge coloring of D can fulfill condition (
ÐÐ→
WO) at all vertices
258 Ars Math. Contemp. 22 (2022) #P2.05 / 249–269
excepting the sink (or the source). Thus, by taking any number, say n, of copies of D
and identifying their sinks (cf. Figure 7) we obtain a connected digraph D′n such that under
any 2-edge coloring at least n of its vertices are ‘defective’ in regard to condition (
ÐÐ→
WO).
A similar construction using the same gadget graph shows that even strong connectedness
comes to no avail in this regard. Namely, take an arbitrary number n ≥ 2 of copies of D,
arrange them in circular order and then identify pairwise the corresponding sink and source
of each neighboring copies (cf. Figure 7). Once again, the obtained strong digraph D′′n
under any 2-edge coloring has at least n ‘defective’ vertices in regard to condition (
ÐÐ→
WO).
The following question comes to mind: Does anything change in regard to this problem if
we confine to simple digraphs, or even more so, to digraphs with simple underlying graphs?
The next result answers the question in negative.
Figure 7: The digraph D′3 (left), and the digraph D
′′
6 (right).
Proposition 2.6. For any given positive integer n, there exists a strongly connected digraph
D with simple underlying graph G(D) such that under any 2-edge coloring of D at least
n of its vertices are ‘defective’ in regard to condition (
ÐÐ→
WO).
Proof. Simply take D to be a complete subdivision of D′′n. In other words, subdivide (at
least once) each arc e ∈ A(D′′n) and orient the newly formed arcs consistently with e.
Given a digraph D, let def(D), the defect of D, denote the minimum number of ‘defec-
tive vertices’ in regard to condition (
ÐÐ→
WO) taken over all 2-edge colorings of D. A question
that naturally arises is whether this parameter can be effectively determined. As it turns
out, the parameter def(D) is closely related to yet another graph construction, relating a
simple graph GD to each digraph D, which we describe next.
Start from the induced subgraph BC(D) ⊆ PS(D) that consists of the ‘bad compo-
nents’ of PS(D) in regard to the requirement of Theorem 2.2; in other words,
V (BC(D)) = ⋃K V (K), where the union is taken over all components K of PS(D)
such that V (K) ∩ V2 is odd-sized and V (K) ∩ V3 is empty.
Thus, the vertex set of GD consists of vertices vK corresponding to components K of
BC(D). As for the edge set of GD, make two distinct vertices vK′ and vK′′ adjacent if
the respective bad components K ′ and K ′′ contain the ‘halves’ v+ and v− of some vertex
C. Hernández-Cruz et al.: Notes on weak-odd edge colorings of digraphs 259
v ∈ V (D). To exemplify, we shall make use of the digraphs D′n and D′′n defined above. For
the first of these digraphs, it is readily seen that each of the n+ 1 nonempty components of
PS(D′n) is bad, and that GD′n =K1,n (cf. Figure 8).
Figure 8: The graph BC(D′3) (left) with each dotted line matching the two ‘halves’ of a
splitted vertex of D′3, and the graph GD′3 =K1,3 (right).
Similarly, each of the 2n nonempty components of PS(D′′n) is bad; this time it holds
that GD′′n = C2n (cf. Figure 9).
Interestingly, any simple graph G is a realization of some GD.
Proposition 2.7. For any simple graph G there exists a digraph D such that GD = G.
Proof. Let n = n(G) and m = m(G) be the order and size of G, respectively. An open
2m-necklace is a digraph obtained as follows: take a path P of length 2m, replace each
edge e ∈ E(P ) by a pair of parallel edges, and then orient each such pair consistently so
that with any natural ordering the vertices become: sink, source, sink, . . ., source, sink
(cf. Figure 10).
Take n disjoint open 2m-necklaces, and enumerate them as D1, . . . ,Dn. Consider an
enumeration of the set E(G) = {e1, . . . , em}. For each i ∈ {1, . . . , n}, fix a natural ordering
of the vertices of Di, and enumerate them accordingly as e0,i, e+1,i, e
−
1,i, . . . , e
+
m,i, e
−
m,i.
Let D be the digraph obtained from D1 ⊍ ⋯ ⊍Dn as follows. Take an enumeration of
the vertex set V (G) = {v1, . . . , vn}. For each ek ∈ E(G), if ek = vivj with i < j, then
identify e+k,i with e
−
k,j . Observe that, by construction:
• PS(D) has n nonempty components;
• each such component belongs to BC(D);
• GD = G.
The last item concludes our proof.
Recall that a matching in a graph is a set of pairwise nonadjacent edges that are not
loops. If M is a matching, the two ends of each edge of M are said to be matched under
M , and each vertex incident with an edge of M is said to be covered by M . A maximum
260 Ars Math. Contemp. 22 (2022) #P2.05 / 249–269
Figure 9: The graph BC(D′′6 ) (left) with each dotted line matching the two ‘halves’ of a
splitted vertex of D′′6 , and the graph GD′′6 = C12 (right).
Figure 10: The open 4-necklace.
matching in a given graph covers as many vertices as possible. The maximum matching
problem is the problem of finding a maximum matching in a given graph G. The num-
ber of edges in such a matching is called the matching number of G and denoted α′(G).
Thanks to the pioneering work of Tutte and Edmonds, the maximum matching problem is
known to be solvable in polynomial time. In particular, one of the 1965 papers of Edmonds
on polyhedral combinatorics, describes, among other things, the so-called Blossom Algo-
rithm [7] (see also [2], pp. 452)), an O(n2m) algorithm that finds a maximum matching
in any given graph of order n and size m. Over the years, various improvements of the
Blossom Algorithm have been found (see, e.g., [14], pp. 422–423).
Our next result establishes a relationship between the defect def(D) of any given di-
graph D and the order n(GD) and matching number α′(GD) of the corresponding simple
graph GD.
Theorem 2.8. For every digraph D, def(D) = n(GD) − α′(GD) holds.
Proof of Theorem 2.8. By Theorems 2.1 and 2.2, we may assume that χ′wo(D) = 3. Take
an arbitrary edge coloring φ of D with color set {1,2}. For simplicity, we use the same no-
tation φ to denote the inherited edge coloring of PS(D). Let PS(D)1 and PS(D)2 be the
spanning subgraphs of PS(D) whose respective edge sets are the color classes φ−1(1) and
φ−1(2). For every vertex x ∈ V (PS(D)), we abbreviate dPS(D)1(x) to d1(x), and likewise
dPS(D)2(x) to d2(x). Consider the partition {V (D)∩V (PS(D)), V (D)/V (PS(D))} of
V (D), and observe the following:
• a vertex u ∈ V (D) ∩ V (PS(D)) is ‘defective’ if and only if both d1(u) and d2(u)
C. Hernández-Cruz et al.: Notes on weak-odd edge colorings of digraphs 261
are odd;
• a vertex v ∈ V (D)/V (PS(D)) is ‘defective’ if and only if some v± ∈ {v+, v−} is a
nonisolated vertex of PS(D) such that both d1(v±) and d2(v±) are even (possibly
zero); call every such v± a ‘defective half-vertex’ originating from v.
First we show that each bad component of PS(D) ‘contains’ at least one defective
vertex.
Claim 2.8.1. Each component K of BC(D) contains a defective vertex or a defective
half-vertex.
Proof of Claim 2.8.1. Let K1 =K ∩PS(D)1 and K2 =K ∩PS(D)2. Since K is an even
graph, clearly OddV (K1) = OddV (K2) and EvenV (K1) = EvenV (K2). By the above
observations, within V (K), the defective vertices constitute the set V1 ∩OddV (K1) and
the defective half-vertices constitute the set V2 ∩ EvenV (K1). In order to show that the
union of these two sets is nonempty it suffices to note that
(V1 ∩OddV (K1)) ∪ (V2 ∩EvenV (K1)) = (V2 ∩ V (K))⊕OddV (K1) , (2.1)
the right-hand side being the symmetric difference of V2∩V (K) and OddV (K1). Now ob-
serve that V2∩V (K) is odd-sized by the assumption that K is bad. And, since OddV (K1)
is even-sized by the handshake lemma, we conclude that (V2 ∩ V (K)) ⊕ OddV (K1) is
odd-sized. Thus, the union of (2.1) is indeed nonempty, i.e., K contains a defective vertex
or a defective half-vertex.
We shall establish the desired equality def(D) = n(GD) − α′(GD) by showing that
each of the two opposed inequalities def(D) ≥ n(GD) −α′(GD) and def(D) ≤ n(GD) −
α′(GD) holds. In order to demonstrate the former inequality, we will need the following
auxiliary result.
Claim 2.8.2. Let G[X,Y ] be a simple bipartite graph such that for each vertex v ∈ X
the degree dG(v) is at most 2 and for each vertex w ∈ Y the degree dG(w) is positive. If
∣X ∣ =m and ∣Y ∣ = n then G contains at least n−m pairwise vertex-disjoint 2-paths whose
interior vertices belong to X .
Proof of Claim 2.8.2. Let p2(G) be the maximum size of a set of pairwise vertex-disjoint
2-paths in G with all interior vertices in X . We prove that p2(G) ≥ n −m by induction on
the number x2(G) of 2-vertices2 contained in X . If x2(G) = 0 then every vertex v ∈ X is
of degree at most 1. Since every vertex w ∈ Y is of degree at least 1, we have that
n −m = ∑
w∈Y
1 − ∑
v∈X
1 ≤ ∑
w∈Y
dG(w) − ∑
v∈X
dG(v) = 0 = p2(G) .
Assuming x2(G) ≥ 1, select a 2-vertex v0 ∈X . Define X ′ =X/{v0} and Y ′ = Y /NG(v0),
and let m′ = ∣X ′∣ and n′ = ∣Y ′∣; thus, m′ = m − 1 and n′ = n − 2. Note that the induced
subgraph G′[X ′, Y ′]meets the degree conditions. Since x2(G′) = x2(G)−1, the inductive
hypothesis gives n′ −m′ ≤ p2(G′). Therefore, as clearly p2(G′) ≤ p2(G) − 1, we deduce
that
n −m = (n′ −m′) + 1 ≤ p2(G′) + 1 ≤ p2(G) ,
which completes the inductive argument.
2A vertex v of a graph G is said to be a d-vertex if dG(x) = d.
262 Ars Math. Contemp. 22 (2022) #P2.05 / 249–269
We are ready to show one of the two opposed inequalities stated above.
Claim 2.8.3. def(D) ≥ n(GD) − α′(GD).
Proof of Claim 2.8.3. Returning to an arbitrary edge coloring φ of D with color set {1,2},
we construct a simple bipartite graph G[X,Y ] as follows. Let X be the set of defective
vertices in D under φ. Let Y be the set of components of BC(D). Join a defective vertex
v with a bad component K if K contains v or contains a defective half-vertex originating
from v. By Claim 1, the obtained graph G[X,Y ] meets the requirements of Claim 2.
Consequently, there are n(GD)− ∣X ∣ pairwise disjoint 2-paths in G[X,Y ] whose interiors
belong to X . However, this clearly gives a matching in GD of size n(GD) − ∣X ∣; simply
for every such 2-path y1xy2 from G[X,Y ] assign the edge vy1vy2 to the matching of GD.
We conclude that α′(GD) ≥ n(GD) − ∣X ∣. Equivalently, ∣X ∣ ≥ n(GD) − α′(GD). The
arbitrariness of φ yields the desired inequality.
In order to complete the proof of Theorem 2.8 we also need to prove the opposite
inequality.
Claim 2.8.4. def(D) ≤ n(GD) − α′(GD).
Proof of Claim 2.8.4. Consider a maximum matching M = {vK2i−1vK2i ∶ 1 ≤ i ≤ k} in
GD. Returning to PS(D), for each i ∈ {1, . . . , k} let vi ∈ V2 be a vertex such that {v+i , v−i }
intersects both K2i−1 and K2i. We color the edges of each nonempty component K of
PS(D) as described below. And for this, we define first an even-sized subset T of V (K):
• If K ∈ {K1,K2, . . . ,K2k} then define T = (V (K) ∩ V2)/{v+1 , v−1 , . . . , v+k , v−k}.
The intersection V (K) ∩ V2 is odd-sized and contains precisely one of the vertices
v+1 , v
−
1 , . . . , v
+
k , v
−
k ; hence, T is even-sized.
• If K is a component of BC(D) −⋃2ki=1Ki then there exists wK ∈ V2 such that the in-
tersection {w+K ,w−K}∩V (K) is a singleton; moreover, the ‘other half’ of {w+K ,w−K}
does not fall into another component of BC(D) −⋃2ki=1Ki, by the maximality of M .
Define T = (V (K) ∩ V2)/{w+K ,w−K}. Again, V (K) ∩ V2 is odd-sized and only one
of the vertices w+K ,w
−
K falls inside V (K) ∩ V2; consequently, T is even-sized.
• If K is not a component of BC(D) then (as in the proof of Theorem 2.2) we distin-
guish between two options: in case V (K)∩V2 is even-sized, define T = V (K)∩V2;
otherwise, as V (K) ∩ V3 ≠ ∅, select an odd-sized subset S ⊆ V (K) ∩ V3 and define
T = (V (K) ∩ V2) ∪ S. Obviously, T is even-sized.
By construction, T is always an even-sized subset of V (K). Therefore, there exists
a T -join H of K. Color E(H) with 1 and E(K)/E(H) with 2. After this has been
done for every component K of PS(D), consider the inherited edge coloring of D. The
set of its defective vertices is precisely R = {v1, . . . , vk} ∪ {wK ∶ K is a component of
BC(D) −⋃2ki=1Ki}. Indeed, by construction we have the following:
• no vertex u ∈ V (D) ∩ V (PS(D)) is defective because one of the colors 1 and 2
has an odd number of appearances on each of the odd-sized semi-cuts of u (as both
d1(u) and d2(u) are even);
C. Hernández-Cruz et al.: Notes on weak-odd edge colorings of digraphs 263
• a vertex v ∈ V (D)/V (PS(D)) is defective if and only if v ∈ R because those are the
only v’s for which some v± ∈ {v+, v−} is a nonisolated vertex of PS(D) such that
both d1(v±) and d2(v±) are even (possibly zero).
Thus, the total number of defective vertices equals n(GD) − α′(GD), which confirms the
desired inequality def(D) ≤ n(GD) − α′(GD).
Proof of Theorem 2.8, continued: From Claims 2.8.3 and 2.8.4 it follows that def(D) =
n(GD) − α′(GD).
Let us reconsider our examples. Since GD′n =K1,n and GD′′n = C2n, we have n(GD′n) =
n + 1 and α′(GD′n) = 1, whereas n(GD′′n) = 2n and α
′(GD′′n) = n; thus, in view of Theo-
rem 2.8, def(D′n) = def(D′′n) = n.
Note that Theorem 2.8 and Proposition 2.7 combined provide an answer to our previous
question about the complexity of finding the defect of a digraph.
Proposition 2.9. The parameter def(D) can be determined in polynomial time. Moreover,
the problem of finding the defect of a digraph is polynomially equivalent to the problem
finding the matching number of a graph.
Another immediate consequence of Theorem 2.8 is the following.
Corollary 2.10. For every digraph D it holds that
⌈n(GD)
2
⌉ ≤ def(D) ≤ n(GD) .
With all being said, it is clear that, in general, there is no ‘directed analogue’ of Propo-
sition 2.5, which served as our initial motivation here. In other words, there are digraphs
that have arbitrarily many ‘defective vertices’.
3 Characterizations in terms of χ′wo and def
We consider two classes of digraphs: the class AD = {D(G) ∶ G is a pseudograph} of
digraphs D(G) that are associated to graphs G, and the class T of tournaments.
3.1 Associated digraphs
We shall use here an additional convention hinted in the introduction. Namely, define
χ′wo(G) = ∞ for each graph G that contains ‘isolated loops’. The following theorem
characterizes the associated digraphs in terms of their weak-odd chromatic index.
Theorem 3.1. For any connected graph G, it holds that
χ′wo(D(G)) =
⎧⎪⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎪⎩
0 if G =K1,
1 if G is an odd graph,
3 if G is an even bipartite graph of odd order ≥ 3,
2 otherwise.
264 Ars Math. Contemp. 22 (2022) #P2.05 / 249–269
. Let D =D(G). It always holds that
χ′wo(D) ≤ χ′wo(G) . (3.1)
Indeed, say φ is a weak-odd χ′wo(G)-edge coloring of G. The accompanying edge col-
oring φD of D assigns to any pair of arcs stemming from an edge e in G color φ(e).
Consequently, φD is a weak-odd χ′wo(G)-edge coloring of D(G), which settles (3.1).
Thus, the nontrivial part of Theorem 3.1 amounts to showing the following equivalence:
χ′wo(D) = 3 ⇔ G is an even bipartite graph of odd order n(G) ≥ 3 . (3.2)
In view of inequality (3.1) and Theorem 1.1, we may confine to G being an even graph of
odd order n(G) ≥ 3. With that assumption, clearly PS(D) = BG(D) and V1 = V3 = ∅.
Therefore, by Theorem 2.2, the equality χ′wo(D) = 3 holds true if and only if some
nonempty component of BG(D) is of odd order. Consequently, the proof of equiva-
lence (3.2) will be complete if we establish the following two assertions.
Claim 3.1.1. If G bipartite, then BG(D) = G ⊍ G, i.e., BG(D) consists of two vertex-
disjoint copies of G.
Claim 3.1.2. If G is not bipartite, then BG(D) is connected.
A moment’s reflection reveals that Claim 3.1.1 is implied by the definitions of ‘as-
sociated digraph’ and ‘split’. For if G = G[V1, V2] is a bipartite graph with bipartition
(V1, V2), then BG(D) = G[V +1 , V −2 ]⊍G[V −1 , V +2 ], that is, BG(D) is the disjoint union of
two bipartite graphs, with respective bipartitions (V +1 , V −2 ) and (V −1 , V +2 ), each of which
is isomorphic to G.
As for the demonstration of Claim 3.1.2, let x, y be an arbitrary pair of (not necessarily
distinct) vertices of G (and thus of D). In order to show the existence of an x+-y− walk
in BG(D), it suffices to find an x-y walk of odd length in G. Indeed, any such walk
W ∶ xv1v2⋯v2ky would yield a walk W ± ∶ x+v−1 v+2⋯v−2k−1v+2ky− in BG(D).
Consider an odd cycle C of G. Let P and Q, respectively, be an x-C and a y-C path in
G. Denote by vx and vy the (not necessarily distinct) endpoints of P and Q in C. Of the
two vxvy arcs of C, let L be the one whose length is of opposite parity than the combined
length ℓP + ℓQ of P and Q. Then P ∪L∪Q gives rise to a desired x-y walk of odd length.
A similar argument proves the existence of an x+-y+ walk in BG(D); it suffices to find
an x-y walk of even length in G, which can be done by using the other vxvy arc of C in the
previous argument. The existence of x−-y+ and x−-y− walks in BG(D) for an arbitrary
pair of vertices x and y in G now follows by symmetry.
An immediate consequence of Theorem 3.1 and inequality (3.1) is the following.
Corollary 3.2. If G is a connected graph, then χ′wo(D(G)) ≤ χ′wo(G). Moreover, equality
holds unless G is an even nonbipartite graph of odd order.
Let us characterize the associated digraphs in terms of their defect.
Proposition 3.3. For any connected graph G, it holds that
def(D(G)) =
⎧⎪⎪⎨⎪⎪⎩
1 if G is an even bipartite graph of odd order ≥ 3,
0 otherwise.
C. Hernández-Cruz et al.: Notes on weak-odd edge colorings of digraphs 265
Proof. By Theorem 3.1, unless G is an even bipartite graph of odd order n(G) ≥ 3, it holds
that def(D(G)) = 0. On the other hand, assuming G is an even bipartite graph of odd order
n(G) ≥ 3, by the proof of Theorem 3.1, PS(D) = BG(D) = G⊍G. Thus, BC(D) = G⊍G
and GD(G) =K2. Consequently, by Theorem 2.8, def(DG) = 1.
Taking into account the established inequality def(D(G)) ≤ 1, one naturally wonders if
an analogue of Proposition 2.5 holds for all associated digraphs. The following proposition
answers this in the positive.
Proposition 3.4. Every connected associated digraph D admits a 2-edge coloring such
that condition (
ÐÐ→
WO) is satisfied at each vertex apart from a prescribed vertex v ∈ V (D).
Proof. Let D = D(G). We may assume that G is an even bipartite graph of odd order
n(G) ≥ 3. As already observed in the proof of Proposition 3.3, it holds that PS(D) = G⊍G.
Let T = V (G)/{v}, and take a T -join H of G. Color the edges of PS(D) with color set
{1,2} as follows: in each copy of G, color E(H) by 1 and E(G)/E(H) by 2. The
inherited 2-edge coloring of D meets the requirements.
3.2 Tournaments
In view of Proposition 2.4, there exist tournaments that require three colors for a weak-odd
edge coloring; namely, as every tournament of odd order with a single peripheral vertex
meets the requirements of the aforementioned proposition, its weak-odd chromatic index
equals 3. Our characterization below asserts that those tournaments are the only ‘excep-
tions’ to weak-odd 2-edge colorability in the class T . The proof shall make use of the
following classical results on tournaments.
Given a digraph D, spanning directed paths and cycles are referred to as hamiltonian
paths and hamiltonian cycles, respectively. Back in 1959, Camion [3] proved that a non-
trivial tournament is strong if and only if it contains a hamiltonian cycle. (In fact, this basic
result was later on improved, first by Harary and Moser [8], and shortly after by Moon,
see, e.g., [9], but for our purposes the initial result of Camion will suffice.) Another basic
theorem on tournaments of an even earlier date, due to Rédei [13], is that every tourna-
ment (not necessarily strong) has a hamiltonian path. (In fact, Rédei [13] proved that every
tournament contains an odd number of hamiltonian paths.)
Theorem 3.5. For any tournament T , it holds that
χ′wo(T ) =
⎧⎪⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎪⎩
0 if T =K1,
1 if T is nontrivial and every vertex semi-degree is odd or zero,
3 if T is nontrivial, of odd order, and has just one peripheral vertex,
2 otherwise.
Proof. For simplicity of presentation, call every nontrivial tournament of odd order having
only one peripheral vertex bad and call every other tournament good. By Proposition 2.4
and Theorem 2.1, the nontrivial aspect of the proof consists of showing that:
Every good tournament is weak-odd 2-edge colorable.
Consider a good tournament T . If it has two peripheral vertices, then the following
furnishes a weak-odd 2-edge coloring: take a hamiltonian path P of T , color A(P ) with
266 Ars Math. Contemp. 22 (2022) #P2.05 / 249–269
1 and the rest of A(T ) with 2. Since the initial (resp. terminal) vertex of P is the source
(resp. sink) of T , color 1 satisfies condition(
ÐÐ→
WO) at all vertices of T . Similarly, if every
strong component of T is nontrivial, then a simple construction of a weak-odd 2-edge
coloring can be obtained as follows: in every strong component K of T take a hamiltonian
cycle CK , color ⋃K A(CK) with 1 and the rest of A(T ) with 2. Then, color 1 meets
condition (
ÐÐ→
WO) everywhere.
Hence, we may assume that there exist a nontrivial peripheral strong component and
a trivial strong component of T . We complete the proof by distinguishing between two
cases.
Case 1: Both peripheral strong components of T are nontrivial. Let Ki and Kt be the
initial and terminal strong components of T . There exists a directed Ki-Kt path P in T
that passes through every vertex v ∉ V (Ki) ∪ V (Kj). Indeed, simply take a hamiltonian
path in the ‘multitournament’ T /{Ki,Kt}, i.e., the directed multigraph obtained from T
by contracting V (Ki) and V (Kt) into a pair of new vertices. By the above assumptions,
the path P is of length ℓ(P ) > 1. Denote by x and y, respectively, the initial and terminal
vertex of P . Thus, the arc xy ∈ A(T )/A(P ). Let Ci and Ct, respectively, be hamiltonian
cycles in Ki and Kj . The arc set A(Ci)∪A(P )∪{xy}∪A(Ct) induces a spanning subdi-
graph of T with all semi-degrees odd. By coloring A(Ci) ∪A(P ) ∪ {xy} ∪A(Ct) with 1
and the rest of A(T ) with 2 we complete a weak-odd 2-edge coloring of T , because color
1 meets condition (
ÐÐ→
WO) everywhere.
Case 2: One peripheral strong component of T is trivial. Since T is good, it has even order.
We may assume T has a sink, say y. Let Ki be the initial strong component of T , and Ci be
a hamiltonian cycle in Ki. If V (T ) = V (Ki) ∪ {y}, then we are done by coloring A(Ci)
with 1 and the rest of A(T ) with 2. Namely, color 2 meets condition (ÐÐ→WO) at y, and color
1 takes care of every other vertex.
Assuming V (T ) ≠ V (Ki) ∪ {y}, take a directed Ki-y path P in T that passes through
every vertex v ∉ V (Ki) (a hamiltonian path in the ‘multitournament’ T /Ki, the directed
multigraph obtained from T by contracting V (Ki) into a vertex, will do). Let x be the
initial vertex of P ; thus, V (Ci) ∩ V (P ) = {x}. By our latest assumption, the arc xy ∉
A(P ). Consequently, the arc set A(Ci) ∪A(P ) ∪ {xy} induces a spanning subdigraph of
T such that both the semi-degrees of y are even whereas the rest of the semi-degrees are
odd. Therefore, as dT (y) is odd, by coloring A(Ci) ∪A(P ) ∪ {xy} with 1 and the rest of
A(T ) with 2 we obtain a weak-odd 2-edge coloring of T . Indeed, once again color 2 meets
condition (
ÐÐ→
WO) at y, and color 1 takes care of every other vertex.
Let us characterize the members of the class T in terms of their defect.
Proposition 3.6. For any tournament T , it holds that
def(T ) =
⎧⎪⎪⎨⎪⎪⎩
1 if T is nontrivial, of odd order, and just one vertex semi-degree is zero,
0 otherwise.
Proof. By Theorem 3.5, we may assume that T is nontrivial, of odd order, and just one
vertex semi-degree is zero. Say T has a sink y. Apply to E(T ) the particular 2-edge
coloring(s) constructed for Case 2 in the proof of Theorem 3.5. Observe that condition
(ÐÐ→WO) is satisfied at each vertex apart from y.
C. Hernández-Cruz et al.: Notes on weak-odd edge colorings of digraphs 267
Therefore, as for the class of associated digraphs, the inequality def(T ) ≤ 1 holds for
every tournament T . Our final proposition shows that an analogue of Proposition 2.5 also
holds for all tournaments.
Proposition 3.7. Every tournament T admits a 2-edge coloring such that condition (
ÐÐ→
WO)
is satisfied at each vertex apart from a prescribed vertex v ∈ V (T ).
Proof. Again, we may assume that T is nontrivial, of odd order, and with just one periph-
eral vertex, say a sink y. Note that BG(T ) has only two components, and moreover, one of
those components consists of the isolated vertex y+. Indeed, by our assumptions, every ver-
tex w ∈ V (T )/{y} dominates y and has d−T (w) > 0; hence, the component containing y−
also includes both w+ and w−. Consequently, PS(T ) has only one nonempty component
K and only one empty component {y+}. Observe that V (K)∩V2 = V2/{y+} is odd-sized,
and V3 = ∅. Define an even-sized subset S ⊆ V (K) as follows:
• if v ∈ V1 then S = {v} ∪ (V2/{y+});
• if v ∉ V1 then S = V2/{v−, y+}.
The rest should be clear. We simply take an S-join H of K, and then color E(H) with 1
and E(K)/E(H) with 2. The inherited 2-edge coloring of T meets the requirements.
4 Concluding remarks and further work
For a graph G (resp. digraph D), an edge covering with color set S is a mapping that assigns
to each edge of G (resp. arc of D) a nonempty subset of S; what distinguishes coverings
from colorings is that we allow more than one color per edge (resp. arc). Related notions
to weak-odd edge colorings of graphs and digraphs, respectively, are the weak-odd edge
coverings defined as edge coverings such that conditions (WO) and (
ÐÐ→
WO) are fulfilled. It
is known that most of the graphs and digraphs are weak-odd 3-edge colorable. Can a color
always be saved by switching to coverings? The answer to this question in the realm of
graphs is affirmative. Indeed, the following holds true.
Proposition 4.1. Any connected graph G whose edge set does not consist entirely of loops,
admits a weak-odd 2-edge covering such that the intersection of color classes is contained
within a prescribed singleton {e} ⊆ E(G).
Proof. By Theorem 1.1, we may assume that G is a nontrivial even graph of odd order.
Subdivide the edge e, and take an odd factor H of the obtained graph. Color E(G)∩E(H)
with 1, E(G)/(E(H) ∪ {e}) with 2, and assign both colors 1 and 2 to the edge e. It is
readily seen that the constructed edge covering meets the requirements.
Following this line of reasoning, we find the next question interesting.
Question 4.2. Does every digraph admit a weak-odd 2-edge covering?
Presuming Question 4.2 answers in positive, define ovl(D), the overlapping of D, to
be the minimum possible size of the intersection of the two color classes in an arbitrary
weak-odd 2-edge covering of D. In view of the families of digraphs D′n and D
′′
n (de-
picted in Figure 7), it is easily seen that ovl(D) is not bounded over the class of digraphs;
moreover, it can acquire any possible value from the set of naturals. We are tempted to
268 Ars Math. Contemp. 22 (2022) #P2.05 / 249–269
wonder whether this parameter also relates to some ‘classical graph parameter’, much as
like def(D) relates to the maximum matching number of graphs.
Following the direction explored in Section 3, it may be interesting to characterize
other digraph families in terms of their weak-odd chromatic index and their defect. Since
tournaments proved to have a nice behavior with respect these parameters, a natural next
step is to consider families of digraphs generalizing tournaments.
Three classic generalizations of tournaments that come to mind are semicomplete di-
graphs, extended tournaments and multipartite tournaments. A digraph is semicomplete
if it is obtained from a complete graph by replacing each edge uv by the arc (u, v), the
arc (v, u) or the pair of arcs (u, v) and (v, u). An extended tournament is a digraph ob-
tained from a tournament by blowing up some of its vertices into stable sets. A multipartite
tournament is an orientation of a complete multipartite graph.
Problem 4.3. Characterize the families of semicomplete digraphs, extended tournaments
and multipartite tournaments in terms of their weak-odd chromatic index.
We think that the following question should be addressed before stating the analogous
problem for the characterization in terms of the defect.
Question 4.4. Is there a constant c such that def(D) ≤ c for every digraph D such that
• D is semicomplete?
• D is an extended tournament?
• D is a multipartite tournament?
A positive answer for Question 4.4 would open the door to consider the following
problem.
Problem 4.5. Characterize the families of semicomplete digraphs, extended tournaments
and multipartite tournaments in terms of their defect.
ORCID iDs
César Hernández-Cruz https://orcid.org/0000-0002-5867-3801
Mirko Petruševski https://orcid.org/0000-0001-8048-7418
Riste Škrekovski https://orcid.org/0000-0001-6851-3214
References
[1] J. Bang-Jensen and G. Z. Gutin, Digraphs. Theory, Algorithms and Applications, Springer,
London, 2nd edition, 2009, doi:10.1007/978-1-84800-998-1.
[2] J. A. Bondy and U. S. R. Murty, Graph Theory, Springer, New York, 2008, https://link.
springer.com/book/9781846289699.
[3] P. Camion, Chemins et circuits hamiltoniens des graphes complets, C. R. Acad. Sci., Paris 249
(1959), 2151–2152.
[4] P. Cheilaris, B. Keszegh and D. Pálvölgyi, Unique-maximum and conflict-free coloring for
hypergraphs and tree graphs, SIAM Journal on Discrete Mathematics 27 (2013), 1775–1787,
doi:10.1137/120880471.
C. Hernández-Cruz et al.: Notes on weak-odd edge colorings of digraphs 269
[5] J. Czap and S. Jendrol’, Colouring vertices of plane graphs under restrictions given by faces,
Discuss. Math. - Graph Theory 29 (2009), 521–543, doi:10.7151/dmgt.1462.
[6] J. Czap, S. Jendrol’, F. Kardoš and R. Soták, Facial parity edge colouring of plane pseudo-
graphs, Discrete Math. 312 (2012), 2735–2740, doi:10.1016/j.disc.2012.03.036.
[7] J. Edmonds, Paths, trees, and flowers, Can. J. Math. 17 (1965), 449–467, doi:10.4153/
CJM-1965-045-4.
[8] F. Harary and L. Moser, The theory of round robin tournaments, Am. Math. Mon. 73 (1966),
231–246, doi:10.2307/2315334.
[9] J. W. Moon, Topics on Tournaments in Graph Theory, Dover Publications, Inc., Mineola, New
York, 2015.
[10] M. Petruševski, A note on weak odd edge-colorings of graphs, Adv. Math. Sci. J. 4
(2015), 7–10, https://www.researchgate.net/publication/297020049_A_
NOTE_ON_WEAK_ODD_EDGE-COLORINGS_OF_GRAPHS.
[11] M. Petruševski and R. Škrekovski, Weak-odd edge-coloring of digraphs, Mat. Bilt. 37 (2013),
61–74, doi:10.37560/matbil13100061p.
[12] L. Pyber, Covering the edges of a graph by..., in: Sets, Graphs and Numbers, Colloquia Mathe-
matica Societatis János Bolyai, volume 60, pp. 583–610, 1991, https://korandi.org/
setsgraphsnumbers.html.
[13] L. Rédei, Ein kombinatorischer Satz, Acta Litt. Sci. Szeged 7 (1934), 39–43, http://pub.
acta.hu/acta/customer/showVolume.ftl.
[14] A. Schrijver, Combinatorial optimization. Polyhedra and efficiency (3 volumes), volume 24
of Algorithms Comb., Springer, Berlin, 2003, https://link.springer.com/book/
9783540443896.