“School of Mathematics”
Back to Papers HomeBack to Papers of School of Mathematics
Paper IPM / M / 7999  


Abstract:  
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 L_{v} of size f(v), such that G has a unique
vertex coloring with these lists, then G is fchoosable. This
implies that, if ∑_{v ∈ V(G)}f(v)=m+n, then there is no list
assignment L such that L_{v}=f(v) for any v ∈ V(G), and
G is uniquely Lcolorable. Finally, we prove that if G is a
connected nonregular multigraph with a list assignment L of
edges, such that for each edge e=uv,L_{e}=max{d(u),d(v)},
then G is not uniquely Lcolorable and we conjecture that this
result holds for any graph.
Download TeX format 

back to top 