Title of article
ON THE COMPLEXITY OF THE COLORFUL DIRECTED PATHS IN VERTEX COLORING OF DIGRAPHS
Author/Authors
مولا احمدي، اِ. نويسنده Department of Mathematical Sciences, Sharif University of Technology, Tehran, Iran Mollaahmadi, E. , سقاييان، س. نويسنده Department of Computer, Abadan Branch, Islamic Azad University, Abadan, Iran Saqaeeyan, S. , دهقان، ا. نويسنده Faculty of Mathematics and Computer Science, Amirkabir University of Technology, Tehran, Iran Dehghan, A.
Issue Information
فصلنامه با شماره پیاپی 0 سال 2013
Pages
7
From page
1
To page
7
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 (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 (G)-coloring of G such that for every
v 2 V (G), there exists a v-colorful directed path is NP-complete.
Journal title
Transactions on Combinatorics
Serial Year
2013
Journal title
Transactions on Combinatorics
Record number
842153
Link To Document