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\).


05C15 Coloring of graphs and hypergraphs


Zbl 0469.05032
Full Text: DOI