Albertson–Grossman–Haas partial list coloring conjecture

From papers

Let GG be an nn-vertex graph with list-chromatic number χ\chi_{\ell}. For a positive integer tχt\leq\chi_{\ell}, assign each vertex a list of tt colors, and let λt\lambda_t be the minimum, over all such list assignments, of the maximum number of vertices that can be properly colored from their lists. Albertson–Grossman–Haas conjecture. If tχt\leq\chi_{\ell}, then

λttnχ.\lambda_t\geq\frac{tn}{\chi_{\ell}}.

Equivalently, at least tn/χtn/\chi_{\ell} vertices can be colored from every assignment of lists of size tt. The conjecture is known in the cases t=1t=1 and t=χt=\chi_{\ell}, but remains open for 1<t<χ1<t<\chi_{\ell}.

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Sources & referencesView supporting material

Primary source

Glenn G. Chappell, “A Lower Bound for Partial List Colorings”, arXiv:math/9805066 (1998).

Solutions 0

No solutions have been posted yet.