TY - JOUR
ID - 2840
TI - On the complexity of the colorful directed paths in vertex coloring of digraphs
JO - Transactions on Combinatorics
JA - TOC
LA - en
SN - 2251-8657
AU - Saqaeeyan, S.
AU - Mollaahmadi, Esmaeil
AU - Dehghan, Ali
AD - Abadan Branch, Islamic Azad University
AD - Sharif University of Technology .
AD - Amirkabir University of Technology, Tehran, Iran
Y1 - 2013
PY - 2013
VL - 2
IS - 2
SP - 1
EP - 7
KW - Colorful Directed Paths
KW - Computational Complexity
KW - Vertex Coloring
DO - 10.22108/toc.2013.2840
N2 - 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.
UR - https://toc.ui.ac.ir/article_2840.html
L1 - https://toc.ui.ac.ir/article_2840_6a5c24f33fd5a66915e473e2c44ca4aa.pdf
ER -