On the complexity of the colorful directed paths in vertex coloring of digraphs

Abstract

The colorful paths and rainbow paths have been considered by several‎ ‎authors‎. ‎A colorful directed path in a digraph $G$ is a directed path with $chi(G)$ vertices whose colors are different‎. ‎A $v$-colorful directed path is such a directed path‎, ‎starting from $v$‎. ‎We prove that for a given $3$-regular triangle-free digraph $G$ determining whether there is a proper $chi(G)$-coloring of $G$‎ ‎such that for every $v in V (G)$‎, ‎there exists a $v$-colorful directed path is $ mathbf{NP} $-complete‎.