EVERY 2-CHOOSABLE GRAPH IS (2M, M)-CHOOSABLE

A graph G = (V, E) with vertex set V and edge set E is called (a, b)-c hoosable (a greater than or equal to 2b) if for any collection {L(v)\v is an element of V} of sets L(v) of cardinality a there exists a coll ection {C(v)\v is an element of V} of subsets C(v) subset of L(v), \C( v)\ = b, such that C(v) boolean AND C(w) = empty set for all vw is an element of E. Giving a partial solution to a problem raised by Erdos, Rubin, and Taylor in 1979, we prove that every (2, 1)-choosable graph is (2m, m)-choosable for all m > 1. (C) 1996 John Wiley & Sons, Inc.