کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4657468 1343739 2006 7 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
A relation between choosability and uniquely list colorability
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
A relation between choosability and uniquely list colorability
چکیده انگلیسی

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