Rainbow Edge Colouring of Digraphs

An edge coloring of a digraph D is called a P3-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 P3-rainbow edge coloring of a digraph D, at least log2χ(D) colors are necessary and 2 log2χ(D)} colors are enough. One can determine in linear time if a digraph has a P3-rainbow edge coloring with 1 or 2 colors. In this paper, it is proved that determining that a digraph has a P3-rainbow edge coloring with 3 colors is an NP-complete problem even for planar digraphs. Moreover, it is shown that log2χ(D) colors is neces-sary and sufficient for a P3-rainbow edge coloring of a transitive orientation digraph D.