“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 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.
Download TeX format |
|
| back to top | |
