کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4649064 | 1632448 | 2007 | 7 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
List homomorphisms of graphs with bounded degrees
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله

چکیده انگلیسی
In a series of papers, we have classified the complexity of list homomorphism problems. Here, we investigate the effect of restricting the degrees of the input graphs. It turns out that the complexity does not change (except when the degree bound is two). We obtain similar results on restricting the size of the lists.We contrast these results with facts about variants of the list homomorphism problem, where restricting the degrees can have an important effect on the complexity.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 307, Issues 3–5, 6 February 2007, Pages 386–392
Journal: Discrete Mathematics - Volume 307, Issues 3–5, 6 February 2007, Pages 386–392
نویسندگان
Tomás Feder, Pavol Hell, Jing Huang,