Home » Subject » Graph Theory » Coloring » Vertex coloring

Partial List Coloring

Importance: High ✭✭✭
Author(s): Albertson, Michael O.
Grossman, Sara
Haas, Ruth
Subject: Graph Theory
» Coloring
» » Vertex coloring
Keywords: list assignment
list coloring
Recomm. for undergrads: no
Posted by: Iradmusa
on: May 5th, 2008
Conjecture   Let $ G $ be a simple graph with $ n $ vertices and list chromatic number $ \chi_\ell(G) $. Suppose that $ 0\leq t\leq \chi_\ell $ and each vertex of $ G $ is assigned a list of $ t $ colors. Then at least $ \frac{tn}{\chi_\ell(G)} $ vertices of $ G $ can be colored from these lists.

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 $ (1 - (\frac{ \chi(G) - 1}{\chi(G)} )^t) \cdot n $ vertices of $ G $ 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.
add new comment