• 1
  • 1
  • 2
  • 6
  • 5
  • 6
  • 3
  • 4
IPM
30
YEARS OLD

“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
  Abstract:
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
Clients Logo
Clients Logo
Clients Logo
Clients Logo
Clients Logo
Clients Logo
Clients Logo
Clients Logo
scroll left or right