“School of Mathematics”

Back to Papers Home
Back to Papers of School of Mathematics

Paper   IPM / M / 7999
School of Mathematics
  Title:   A relation between choosability and uniquely list colorability
  Author(s):  S. Akbari (Joint with V. S. Mirrokni and B. S. Sadjad)
  Status:   Published
  Journal: J. Combin. Theory Ser. B
  Vol.:  96
  Year:  2006
  Pages:   577-583
  Supported by:  IPM
Let G be a graph with n vertices and m edges and assume that f:V(G)→ N is a function with ∑vV(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 ∑vV(G)f(v)=m+n, then there is no list assignment L such that |Lv|=f(v) for any vV(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
scroll left or right