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

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
نویسندگان
, , ,