On a conjecture of Erdös, Rubin and Taylor

A graph G with vertex set V and edge set E is called (a; b)-choosable if for any assignment of lists L(v) of colors to the vertices v of G with jL(v)j = a it is possible to choose subsets C(v) ae L(v), jC(v)j = b for every v 2 V such that C(u) " C(v) = ; for all uv 2 E. In 1979, Erdos, Rubin and Taylor raised the conjecture that every (a; b)- choosable graph G is also (am; bm)-choosable for all m ? 1. We investigate the case b = 1, presenting some classes of (a; 1)-choosable graphs for which (am; m)-choosability can be proved for all m. 1 Introduction In the 1970s, Vizing [18] and Erdos, Rubin and Taylor [6] introduced the concepts of lists colorings and choosability of graphs. Let G = (V; E) be a graph with vertex set V and edge set E. Suppose there is an assignment of finite sets L(v) of colors (called the list at v) to the vertices of G. Then the graph G is called L-list colorable if it is possible to color the vertices of G such that adjacent vertices get distinct colors and ..