Choosability in graphs. (English) Zbl 0469.05032

Erdős, Paul; Rubin, Arthur L.; Taylor, Herbert

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

Keywords:

chromatic number; f-choosable; choice \(\#G\); 2-choosable graphs; random bipartite graph

Citations:

Zbl 0435.00002