Article ID Journal Published Year Pages File Type
4657468 Journal of Combinatorial Theory, Series B 2006 7 Pages PDF
Abstract

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.

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics