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 Km,m is not k-choosable (where, of course, \chi(Km,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 2k-1 \leq N(2,k) \leq k22k+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 \thetaa,b,c, denote the \theta graph with arcs of length a, b and c, and let Ck denote the closed circuit of length k. Then G is 2-choosable if, and only if, \hat G = K1, C2m+2 or \theta2,2,2m for m \geq 1. It is shown that the graph choosability problem is a \pi2\rho-complete problem. Also let Rm,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\#Rm,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