کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
8900542 | 1631602 | 2018 | 32 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
On the complexity of generalized chromatic polynomials
ترجمه فارسی عنوان
در پیچیدگی چندجملهایهای کروماتیک تعمیم یافته
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات کاربردی
چکیده انگلیسی
J. Makowsky and B. Zilber (2004) showed that many variations of graph colorings, called CP-colorings in the sequel, give rise to graph polynomials. This is true in particular for harmonious colorings, convex colorings, mcct-colorings, and rainbow colorings, and many more. N. Linial (1986) showed that the chromatic polynomial Ï(G;X) is #P-hard to evaluate for all but three values X=0,1,2, where evaluation is in P. This dichotomy includes evaluation at real or complex values, and has the further property that the set of points for which evaluation is in P is finite. We investigate how the complexity of evaluating univariate graph polynomials that arise from CP-colorings varies for different evaluation points. We show that for some CP-colorings (harmonious, convex) the complexity of evaluation follows a similar pattern to the chromatic polynomial. However, in other cases (proper edge colorings, mcct-colorings, H-free colorings) we could only obtain a dichotomy for evaluations at non-negative integer points. We also discuss some CP-colorings where we only have very partial results.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Advances in Applied Mathematics - Volume 94, March 2018, Pages 71-102
Journal: Advances in Applied Mathematics - Volume 94, March 2018, Pages 71-102
نویسندگان
A. Goodall, M. Hermann, T. Kotek, J.A. Makowsky, S.D. Noble,