%0 Journal Article
%T On the complexity of the colorful directed paths in vertex coloring of digraphs
%J Transactions on Combinatorics
%I University of Isfahan
%Z 2251-8657
%A Saqaeeyan, S.
%A Mollaahmadi, Esmaeil
%A Dehghan, Ali
%D 2013
%\ 06/01/2013
%V 2
%N 2
%P 1-7
%! On the complexity of the colorful directed paths in vertex coloring of digraphs
%K Colorful Directed Paths
%K Computational Complexity
%K Vertex Coloring
%R 10.22108/toc.2013.2840
%X 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.
%U https://toc.ui.ac.ir/article_2840_6a5c24f33fd5a66915e473e2c44ca4aa.pdf