Partial list colorings (Q1972145): Difference between revisions

Let \(R= \{1,2,\dots, r\}\) be a set of colors, and let \(\ell: V(G)\to 2^R\) be a function. A proper coloring \(c: V(G)\to R\) is said to be a list coloring if \(c(x)\in\ell(x)\) for all \(x\). If there is an integer \(s\) such that all functions \(\ell\) with \(|\ell(x)|= s\) have a list coloring, then \(G\) is said to be \(s\)-choosable. The authors conjecture that when \(G\) is \(s\)-choosable, for every \(\ell\) with \(|\ell(x)|= t\) there are at least \(({t\over s})n\) vertices that can be colored by \(\ell\). Lower bounds involving old and new parameters for graphs are proved.