On $(k,k)$-Choosability of Graphs

Abstract

A $(k,t)$-list assignment $L$ of a graph $G$ is a mapping which assigns a set of size $k$ to each vertex $v$ of $G$ and $|\bigcup _{v\in V(G)}L(v)|=t$. A graph $G$ is $(k,t)$-choosable if $G$ has a proper coloring $f$ such that $f(v)\in 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 a $(k+1)$-clique.