@article {
author = {},
title = {$P_3$-Rainbow Edge Colouring of Digraphs},
journal = {Journal of Algorithms and Computation},
volume = {},
number = {},
pages = {1-11},
year = {2022},
publisher = {University of Tehran},
issn = {2476-2776},
eissn = {2476-2784},
doi = {10.22059/jac.2022.85517},
abstract = {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 coloringof a transitive orientation digraph $D$. },
keywords = {planar digraphs,rainbow coloring,transitive digraph,dichromatic index},
url = {https://jac.ut.ac.ir/article_85517.html},
eprint = {https://jac.ut.ac.ir/article_85517_65d76780f65db1c817b88f0d5705fed7.pdf}
}