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

Document Type: Research Paper

Authors

1 Abadan Branch, Islamic Azad University

2 Sharif University of Technology .

3 Amirkabir University of Technology, Tehran, Iran

Abstract

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

Keywords

Main Subjects

References

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.
Transactions on Combinatorics

Volume 2, Issue 2
June 2013
Pages 1-7

Files

Share

How to cite

Statistics