Oriented modular arc colorings in digraphs

Abstract

For a nontrivial connected oriented graph D and a vertex v of D, let E^-_v = {(u,v) ∈ E(D): u ∈ V(D)} and E⁺_v = {(v,u) ∈ E(D): u ∈ V(D)}. For an arc coloring c: E(D) → ℤ_k of D and a vertex v of D, let σ^-(v) = Σ_e∈Ev(e) and σ⁺(v) = Σ_e∈Ev+ c(e), where each sum is performed in ℤ_k. Then the coloring c induces a vertex coloring σ: v(d) → ℤ_k × ℤ_k defined by σ(v) = (σ^-(v), σ⁺(v)) for each vertex v of D and σ(v) is called the color sum of v. If σ(u) ≠ σ(v) for each pair u, v of adjacent vertices in D, then c is an oriented k-modular coloring of D. The minimum k for which L> has an oriented k-modular coloring is the oriented modular chromatic index X'_om(D) of D. For each orientation D of a connected graph G, the number X'_om(D) exists and |√/X(G)] ≤ X'_om(D) ≤ X(G) + 1-It is shown that X'_om(D) = 2 for all orientations D of a tree or a cycle and X'_om(T) = |√n| for every tournament of order n ≥ 2. Furthermore, there is an infinite class of connected graphs G having an orientation D for which X'_om(D) ≠ |√X(G) | and an infinite class of connected graphs having two orientations D₁ and D₂ for which X'_om(D₁) ≠ X'_om(D₂).