کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4657468 | 1343739 | 2006 | 7 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
A relation between choosability and uniquely list colorability
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
Let G be a graph with n vertices and m edges and assume that is a function with ∑v∈V(G)f(v)=m+n. We show that, if we can assign to any vertex v of G a list Lv of size f(v) such that G has a unique vertex coloring with these lists, then G is f-choosable. This implies that, if ∑v∈V(G)f(v)>m+n, then there is no list assignment L such that |Lv|=f(v) for any v∈V(G) and G is uniquely L-colorable. Finally, we prove that if G is a connected non-regular multigraph with a list assignment L of edges such that for each edge e=uv, |Le|=max{d(u),d(v)}, then G is not uniquely L-colorable and we conjecture that this result holds for any graph.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Combinatorial Theory, Series B - Volume 96, Issue 4, July 2006, Pages 577-583
Journal: Journal of Combinatorial Theory, Series B - Volume 96, Issue 4, July 2006, Pages 577-583