The notion of properly colored path/trail also makes sense in directed
graphs equipped with a coloring of their arcs (directed edges). We first look
at PC directed trails and show that they can be found by a simple
breadth-first search algorithm, in linear time (thm:lolbfs). There was
already a polynomial time algorithm for this problem in the
literature [1]}; we examine more precisely
its asymptotic complexity and argue that it is worse than ours
(rem:reload).
