On (k, t)-choosability of graphs

Abstract

A (k, t)-list assignment L of graph G is a mapping which assigns a set of size k to each vertex v of G and | UvεV(G) L(v)\ = t. A graph G is (it, t)-choosable if G has a proper coloring f such that f(v) ε L(v) for each (k, t)-list assignment L. We determine t in terms of k and n that guarantee (k, t)-choosability of any n-vertex graph and a better bound if such graph does not contain (k + l)-clique.