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.