An edge coloring of a digraph $D$ is called a $P_3$-rainbow edge coloring if the edges of any directed path of $D$ with length 2 are colored with different colors. It is proved that for a $P_3$-rainbow edge coloring of a digraph $D$, at least $\left\lceil{log_2{\chi(D)}} \right\rceil$ colors are necessary and $ 2\left\lceil{log_2{\chi(D)}}\right\rceil\}$ colors are enough. One can determine in linear time if a digraph has a $P_3$-rainbow edge coloring with 1 or 2 colors. In this paper, it is proved that determining that a digraph has a $P_3$-rainbow edge coloring with 3 colors is an NP-complete problem even for planar digraphs. Moreover, it is shown that $\left\lceil{log_2{\chi(D)}}\right\rceil$ colors is necessary and sufficient for a $P_3$-rainbow edge coloring of a transitive orientation digraph $D$.
Hasheminezhad, M. (2021). Rainbow Edge Colouring of Digraphs. Journal of Algorithms and Computation, 53(2), 165-172. https://doi.org/10.22059/jac.2021.85350
MLA
Hasheminezhad, M. "Rainbow Edge Colouring of Digraphs", Journal of Algorithms and Computation, 53, 2, 2021, 165-172. doi: 10.22059/jac.2021.85350
HARVARD
Hasheminezhad M. (2021). 'Rainbow Edge Colouring of Digraphs', Journal of Algorithms and Computation, 53(2), pp. 165-172. doi: 10.22059/jac.2021.85350
CHICAGO
M. Hasheminezhad, "Rainbow Edge Colouring of Digraphs," Journal of Algorithms and Computation, 53 2 (2021): 165-172, doi: 10.22059/jac.2021.85350
VANCOUVER
Hasheminezhad M. Rainbow Edge Colouring of Digraphs. J. Algo. Comp. 2021;53(2):165-172. doi: 10.22059/jac.2021.85350
