کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4653181 | 1632757 | 2017 | 11 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Colourings, homomorphisms, and partitions of transitive digraphs
ترجمه فارسی عنوان
رنگآمیزی، همریختی و پارتیشنهای گراف جهت دار انتقالی
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
چکیده انگلیسی
We investigate the complexity of generalizations of colourings (acyclic colourings, (k,ℓ)(k,ℓ)-colourings, homomorphisms, and matrix partitions), for inputs restricted to the class of transitive digraphs. Even though transitive digraphs are nicely structured, many problems are intractable, and their complexity turns out to be difficult to classify. We present some motivational results and several open problems.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: European Journal of Combinatorics - Volume 60, February 2017, Pages 55–65
Journal: European Journal of Combinatorics - Volume 60, February 2017, Pages 55–65
نویسندگان
Tomás Feder, Pavol Hell, César Hernández-Cruz,