Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4657468 | Journal of Combinatorial Theory, Series B | 2006 | 7 Pages |
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