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.
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.
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.
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.
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.
2
S. Akbari, V. Liaghat and A. Nikzad (2011). Colorful paths in vertex coloring of graphs. Electron. J. Combin., Paper 17. 18 (1), 9
3
M. Alishahi, A. Taherkhani and C. Thomassen (2011). Rainbow paths with prescribed ends. Electron. J. Combin., Paper 86. 18 (1), 0
4
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
5
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..
6
H. Li (2001). A generalization of the Gallai-Roy theorem. Graphs Combin.. 17 (4), 681-685
7
C. Lin (2007). Simple proofs of results on paths representing all colors in proper vertex-colorings. Graphs Combin.. 23 (2), 201-203
8
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
9
D.~B. West (1996). Introduction to graph theory. Prentice Hall Inc., Upper Saddle River, NJ.
Top