## Every 2-choosable graph is $$(2m, m)$$-choosable.(English)Zbl 0853.05034

Let $$G = (V,E)$$ be a graph and suppose that a finite set $$L(v)$$ (called the list of colors admissible at vertex $$v)$$ is associated with each $$v \in V$$. Then $$G$$ is called list colorable or is said to admit a list coloring (with respect to the collection $$\{L(v) \mid v \in V\}$$ of lists) if one can choose an $$f(v) \in L(v)$$ for each $$v \in V$$ such that $$f(v) \neq f(w)$$ for all edges $$vw \in E$$. $$G$$ is said to be $$(k,l)$$-choosable $$(k \geq 2l$$ and $$l \geq 1)$$ if every list assignment $$\{L(v) \mid v \in V\}$$, with $$|L(v) |= k$$ for all $$v \in V$$, admits the choice of subsets $$C(v) \subset L(v)$$ of cardinality $$l$$ such that $$C(v) \cap C(w) = \varnothing$$ for every edge $$vw \in E$$. The following conjecture was raised by P. Erdös, A. L. Rubin and H. Taylor [Combinatorics, graph theory and computing, Proc. West Coast Conf., Arcata/Calif. 1979, 125-157 (1980; Zbl 0469.05032)]: For $$k \geq 2l$$, $$l \geq 1$$, $$m \geq 2$$, every $$(k,l)$$-choosable graph is $$(km, lm)$$-choosable. The aim of the present paper is to verify this conjecture for 2-choosable graphs, i.e., $$k = 2$$, $$l = 1$$, for all $$m \geq 2$$.

### MSC:

 05C15 Coloring of graphs and hypergraphs

### Keywords:

list colorable; list coloring

Zbl 0469.05032
Full Text: