##
**Zentralblatt MATH**

**Publications of (and about) Paul Erdös**

**Zbl.No: ** 469.05032

**Autor: ** Erdös, Paul; Rubin, Arthur L.; Taylor, Herbert

**Title: ** Choosability in graphs. (In English)

**Source: ** Combinatorics, graph theory and computing, Proc. West Coast Conf., Arcata/Calif. 1979, 125-157 (1980).

**Review: ** [For the entire collection see Zbl 435.00002.]

Let G = (V,E) be a graph. Given a function f on the nodes which assigns a positive integer f(j) to node j, assign f(j) distinct letters to node j for each j in V. G is f-choosables if, no matter what letters are assigned to each vertex, we can always make a choice consisting of one letter from each node, with distinct letters from each adjacent node. Using the constant function f(j) = k, the choice \#G is equal to k of G is k-choosable but not k-1-chooseable. It is shown that choice \#G \geq \chi(G). In fact, choice \#G \geq \chi(G) is unbounded. As an example, it is shown that if m = \binom{2k-1}{k}, then K_{m,m} is not k-choosable (where, of course, \chi(K_{m,m} = 2)). If we denote by N(2,k) the minimum number of nodes in a graph G such that \chi(G) = 2 but choice \#G > k, Then 2^{k-1} \leq N(2,k) \leq k^{2}2^{k+2}. A characterization of 2-choosable graphs is given. Let \hat G denote the graph obtained from G by deletion of all nodes with valence 1. Also, let \theta_{a,b,c}, denote the \theta graph with arcs of length a, b and c, and let C_{k} denote the closed circuit of length k. Then G is 2-choosable if, and only if, \hat G = K_{1}, C_{2m+2} or \theta_{2,2,2m} for m \geq 1. It is shown that the graph choosability problem is a \pi_{2}^{\rho}-complete problem. Also let R_{m,m} be a random bipartite graph with bipartitions of size m and with \frac{log m}{log6} > 121. If t = \left\lceil\frac{2 log m}{log2}\right\rceil, then with probability > 1-(t!)^{-2} we have \frac{log m}{log6} < choice\#R_{m,m} < \frac{3 log m}{log6}. Finally, it is noted that the interest in this problem arose in trying to prove J. Dinitz's problem. Given an m× m array of m-sets, is it always possible to choose on element from each set, keeping the chosen elements distinct in every row, and distinct in every column. This problem remains unsolved for m \geq 4.

**Reviewer: ** J.Dinitz

**Classif.: ** * 05C15 Chromatic theory of graphs and maps

**Keywords: ** chromatic number; f-choosable; choice \#G; 2-choosable graphs; random bipartite graph

**Citations: ** Zbl.435.00002

© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag