اخبار و اعلانات

 آمار

تعداد نشریات44
تعداد شماره‌ها1,877
تعداد مقالات15,278
تعداد مشاهده مقاله43,731,372
تعداد دریافت فایل اصل مقاله17,563,521
Saqaeeyan, S., Mollaahmadi, Esmaeil, Dehghan, Ali. (1392). On the complexity of the colorful directed paths in vertex coloring of digraphs. , 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". , 2, 2, 1392, 1-7. doi: 10.22108/toc.2013.2840
Saqaeeyan, S., Mollaahmadi, Esmaeil, Dehghan, Ali. (1392). 'On the complexity of the colorful directed paths in vertex coloring of digraphs', , 2(2), pp. 1-7. doi: 10.22108/toc.2013.2840
Saqaeeyan, S., Mollaahmadi, Esmaeil, Dehghan, Ali. On the complexity of the colorful directed paths in vertex coloring of digraphs. , 1392; 2(2): 1-7. doi: 10.22108/toc.2013.2840

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

Transactions on Combinatorics
مقاله 1، دوره 2، شماره 2، شهریور 2013، صفحه 1-7    اصل مقاله (335.62 K)
نوع مقاله: Research Paper
شناسه دیجیتال (DOI): 10.22108/toc.2013.2840
نویسندگان
S. Saqaeeyan* 1؛ Esmaeil Mollaahmadi2؛ Ali Dehghan3
1Abadan Branch, Islamic Azad University
2Sharif University of Technology .
3Amirkabir University of Technology, Tehran, Iran
چکیده
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‎.
کلیدواژه‌ها
Colorful Directed Paths؛ Computational Complexity؛ Vertex Coloring
مراجع
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
آمار
تعداد مشاهده مقاله: 6,645
تعداد دریافت فایل اصل مقاله: 3,735


سامانه مدیریت نشریات علمی. طراحی و پیاده سازی از سیناوب