![](/files/happy5.png)
Partial List Coloring
Conjecture Let
be a simple graph with
vertices and list chromatic number
. Suppose that
and each vertex of
is assigned a list of
colors. Then at least
vertices of
can be colored from these lists.
![$ G $](/files/tex/b8e7ad0330f925492bf468b5c379baec88cf1b3d.png)
![$ n $](/files/tex/ec63d7020a64c039d5f6703b8fa3ab7393358b5b.png)
![$ \chi_\ell(G) $](/files/tex/b68082745a25a09294e2c92c006b61d3ef1a9e54.png)
![$ 0\leq t\leq \chi_\ell $](/files/tex/1aee119babfe25de435c7cf6beff3114a5ae9326.png)
![$ G $](/files/tex/b8e7ad0330f925492bf468b5c379baec88cf1b3d.png)
![$ t $](/files/tex/4761b031c89840e8cd2cda5b53fbc90c308530f3.png)
![$ \frac{tn}{\chi_\ell(G)} $](/files/tex/59b72b19d6799e1fd7a0fc093bff9283068dc838.png)
![$ G $](/files/tex/b8e7ad0330f925492bf468b5c379baec88cf1b3d.png)
Albertson, Grossman, and Haas introduce this interesting question in [AGH], and prove some partial results. For instance, they show that under the above assumptions, at least vertices of
can be colored from the lists.
Bibliography
*[AGH] M. Albertson, S. Grossman and R. Haas, Partial list colouring, Discrete Math., 214(2000), pp. 235-240.
* indicates original appearance(s) of problem.