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

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 ۳-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‎.

کلیدواژه ها:

Colorful Directed Paths ، Computational Complexity ، Vertex Coloring