## Choosability in graphs.(English)Zbl 0469.05032

Combinatorics, graph theory and computing, Proc. West Coast Conf., Arcata/Calif. 1979, 125-157 (1980).
[For the entire collection see Zbl 0435.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^22^{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}<\text{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\times 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

### MSC:

 05C15 Coloring of graphs and hypergraphs

Zbl 0435.00002