On the complexity of the colorful directed paths in vertex coloring of digraphs
Publish place: Transactions on Combinatorics، Vol: 2، Issue: 2
Publish Year: 1392
نوع سند: مقاله ژورنالی
زبان: English
View: 222
This Paper With 7 Page And PDF Format Ready To Download
- Certificate
- من نویسنده این مقاله هستم
استخراج به نرم افزارهای پژوهشی:
شناسه ملی سند علمی:
JR_COMB-2-2_001
تاریخ نمایه سازی: 29 آبان 1400
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 ۳-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:
Authors
S. Saqaeeyan
Abadan Branch, Islamic Azad University
Esmaeil Mollaahmadi
Sharif University of Technology .
Ali Dehghan
Amirkabir University of Technology, Tehran, Iran
مراجع و منابع این Paper:
لیست زیر مراجع و منابع استفاده شده در این Paper را نمایش می دهد. این مراجع به صورت کاملا ماشینی و بر اساس هوش مصنوعی استخراج شده اند و لذا ممکن است دارای اشکالاتی باشند که به مرور زمان دقت استخراج این محتوا افزایش می یابد. مراجعی که مقالات مربوط به آنها در سیویلیکا نمایه شده و پیدا شده اند، به خود Paper لینک شده اند :