A relation between choosability and uniquely list colorability
A relation between choosability and uniquely list colorability
复制标题
DOI：
10.1016/j.jctb.2005.12.001
复制
发表时间：
2006-07
期刊：
影响因子：
--
通讯作者：
S. Akbari;V. Mirrokni;S. Sadjad
中科院分区：
文献类型：
--
作者：
S. Akbari;V. Mirrokni;S. Sadjad
设G是一个n点m边图，f：V（G）→N是一个函数，满足∑v∈V（G）f（v）=m+n.证明了如果G的任意顶点v都能被赋以一个f（v）的链表Lv，使得G的顶点染色唯一，则G是f-可选的.这意味着，如果∑v∈V（G）f（v）>m+n，则不存在列表赋值L使得|LV| =f（v）且G是唯一L-可着色的.最后，我们证明了：如果G是一个连通的非正则多重图，其边的列表分配L使得对于每条边e=uv，|乐|=max{d（u），d（v）}，则G不是唯一L-可染的，并且我们猜想这个结果对任何图都成立.
Let G be a graph with n vertices and m edges and assume that f:V(G)→N 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 Lvof 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.