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

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 |