Choosability of Bipartite Graphs

A graph \(G\) is called \((a:b)\)-choosable if for every assignment of \(a\)-sets \(L(v)\) to the vertices of \(G\) it is possible to choose \(b\)-subsets \(M(v) \subseteq L(v)\) so that adjacent vertices get disjoint subsets. We give a different proof of a theorem of Tuza and Voigt that every \(2\)-choosable graph is \((2k:k)\)-choosable for any positive integer \(k\). Our proof is algorithmic and can be implemented to run in time \(O(k|V(G)|)\).