کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
5777668 1632971 2017 7 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
When does the list-coloring function of a graph equal its chromatic polynomial
ترجمه فارسی عنوان
هنگامی که تابع رنگ بندی یک لیست یک گراف چندضلعی رنگی است
کلمات کلیدی
فهرست رنگ آمیزی، چرخه شکسته، چندجملهای کروماتیک،
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
چکیده انگلیسی
Let G be a connected graph with n vertices and m edges. Using Whitney's broken cycle theorem, we prove that if k>m−1ln⁡(1+2)≈1.135(m−1) then for every k-list assignment L of G, the number of L-colorings of G is at least that of ordinary k-colorings of G. This improves previous results of Donner (1992) and Thomassen (2009), who proved the result for k sufficiently large and k>n10, respectively.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Combinatorial Theory, Series B - Volume 122, January 2017, Pages 543-549
نویسندگان
, , ,