Weak-odd chromatic index of special digraph classes

Abstract

Give a digraph $D=(V(D),A(D))$, let ${\partial }_D^{+}(v)=\{vw|w\in N_D^{+}(v)\}$ and ${\partial }_D^{-}(v)=\{uv|u\in N_D^{-}(v)\}$ be semi-cuts of $v$. A mapping $\phi :A(D)\to [k]$ is called a weak-odd $k$-edge coloring of $D$ if it satisfies the condition: for each $v\in V(D)$, there is at least one color with an odd number of occurrences on each non-empty semi-cut of $v$. We call the minimum integer $k$ the weak-odd chromatic index of $D$. When limit to 2 colors, use $def(D)$ to denote the defect of $D$, the minimum number of vertices in $D$ at which the above condition is not satisfied. In this paper, we give a descriptive characterization about the weak-odd chromatic index and the defect of semicomplete digraphs and extended tournaments, which generalize results of tournaments to broader classes. And we initiated the study of weak-odd edge covering on digraphs.

14 pages, 1 figures