\(T\)-choosability in graphs (Q1383364)

Given a set of nonnegative integers \(T\) and a function \(S\) which assigns a set of integers \(S(v)\) to each vertex \(v\) of a graph \(G\), an \(S\)-list \(T\)-coloring \(c\) of \(G\) is a vertex-coloring (with positive integers) of \(G\) such that \(c(v)\in S(v)\) whenever \(v\in V(G)\) and \(|c(u)-c(w)|\notin T\) whenever \(uw\in E(G)\). For a fixed \(T\), the \(T\)-choice number \(T\text{-ch}(G)\) of a graph \(G\) is the smallest number \(k\) such that \(G\) has an \(S\)-list \(T\)-coloring for every collection of sets \(S(v)\) of size \(k\) each. Exact values and bounds on the \(T_{r,s}\)-choice numbers where \(T_{r,s}=\{0,s,2s,\ldots ,rs\}\) are presented for even cycles, notably that \(T_{r,s} \text{-ch}(C_{2n})=2r+2\) if \(n\geq r+1\). Other bounds are obtained by applying algebraic and probabilistic techniques, such as that \(T\text{-ch}(C_{2n})\leq 2|T|\) if \(0\in T\), and \(c_{1}r \log n\leq T_{r,s} \text{-ch}(K_{n,n})\leq c_{2}r \log n\) for some absolute positive constants \(c_{1}\), \(c_{2}\). Notice that the \(T_{r,s}\)-choice numbers for even cycles were obtained independently by \textit{Barry A. Tesman} in his thesis [\(T\)-colorings, list \(T\)-colorings, and set \(T\)-colorings of graphs, Ph.D. thesis, Dept. Math., Rutgers University, New Brunswick, NJ (1989)].