Every 2-choosable graph is (2m, m)-choosable
Zs. Tuza, Margit Voigt · Journal of Graph Theory · 1996
A graph G = (V, E) with vertex set V and edge set E is called (a,b)-choosable (a ≥ 2b) if for any collection {L(υ)|υ ϵ V} of sets L(υ) of cardinality a there exists a collection {C(υ)|υ ϵ V} of subsets C(υ) ⊂ L(υ), |C(υ)| = b, such that C(υ) ∩ C(w) = 0 for all υw ϵ E. Giving a partial solution to a problem raised by Erdös, Rubin, and Taylor in 1979, we prove that every (2, 1)-choosable graph is (2m, m)-choosable for all m > 1. © 1996 John Wiley & Sons, Inc.