Saqaeeyan, S., Mollaahmadi, E., Dehghan, A. (2013). On the complexity of the colorful directed paths in vertex coloring of digraphs. Transactions on Combinatorics, 2(2), 1-7. doi: 10.22108/toc.2013.2840
S. Saqaeeyan; Esmaeil Mollaahmadi; Ali Dehghan. "On the complexity of the colorful directed paths in vertex coloring of digraphs". Transactions on Combinatorics, 2, 2, 2013, 1-7. doi: 10.22108/toc.2013.2840
Saqaeeyan, S., Mollaahmadi, E., Dehghan, A. (2013). 'On the complexity of the colorful directed paths in vertex coloring of digraphs', Transactions on Combinatorics, 2(2), pp. 1-7. doi: 10.22108/toc.2013.2840
Saqaeeyan, S., Mollaahmadi, E., Dehghan, A. On the complexity of the colorful directed paths in vertex coloring of digraphs. Transactions on Combinatorics, 2013; 2(2): 1-7. doi: 10.22108/toc.2013.2840
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 $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.
S.~Akbari, F.~Khaghanpoor and S.~Moazzeni Colorful paths in vertex coloring of graphs. Preprint.
S. Akbari, V. Liaghat and A. Nikzad (2011). Colorful paths in vertex coloring of graphs. Electron. J. Combin., Paper 17. 18 (1), 9
M. Alishahi, A. Taherkhani and C. Thomassen (2011). Rainbow paths with prescribed ends. Electron. J. Combin., Paper 86. 18 (1), 0
G.~J. Chang, L. D. Tong, J. H. Yan and H. G. Yeh (2002). A note on the Gallai-Roy-Vitaver theorem. Discrete Math.. 256 (1-2), 441-444
M.~R. Garey and D.~S. Johnson (1979). Computers and intractability: A guide to the theory of $NP$-completeness. A Series of Books in the Mathematical Sciences, W. H. Freeman and Co., San Francisco, Calif..
H. Li (2001). A generalization of the Gallai-Roy theorem. Graphs Combin.. 17 (4), 681-685
C. Lin (2007). Simple proofs of results on paths representing all colors in proper vertex-colorings. Graphs Combin.. 23 (2), 201-203
P.~M. Pardalos and A.~Migdalas (2004). A note on the complexity of longest path problems related to graph
coloring. Appl. Math. Lett.. 17 (1), 13-15
D.~B. West (1996). Introduction to graph theory. Prentice Hall Inc., Upper Saddle River, NJ.
Top