Choosability of graphs with infinite sets of forbidden differences (Q2462372)

Suppose \(G\) is a (finite) graph, \(T\) is a set of non-negative integers, and for each vertex \(v\) of \(G\) we are given a set \(L(v)\) of integers. \(G\) is \(T\)-colorable from the list-assigment \(L\) if it is possible to choose for each vertex a color \(c(v)\in L(v)\) in such a way that \(\left| c(v)-c(w)\right| \not\in T\) whenever \(v\) and \(w\) are neighbors. If \(G\) is \(T\)-colorable from every \(L\) that has \(\left| L(v)\right| \geq k\) for every \(v\), then \(G\) is \(T\)-\(k\)-choosable; the \(T\)-choice number of \(G\) is the smallest integer \(k\) such that \(G\) is \(T\)-\(k\)-choosable, if any such \(k\) exists. If \(T\) is infinite then it might seem possible that some nonempty graphs have finite \(T\)-choice numbers, and other graphs do not. The author proves that this cannot happen: if \(K_{2}\) is \(T\)-\(k\)-choosable then a graph \(G\) of maximum degree \(\Delta \) is \(T\)-\(\ell\)-choosable for every \(\ell \geq (k-1)(4e\Delta )^{k}\), and also for every \(\ell \geq ((k-1)+3)k^{\Delta }\). Noting that the first of these lower bounds is polynomial in \(\Delta \) and the second is polynomial in \(k\), he asks whether or not it is possible to find a bound that is polynomial in both \(\Delta \) and \(k\).