Grossman, Sara


Partial List Coloring ★★★

Author(s): Albertson; Grossman; Haas

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.

Keywords: list assignment; list coloring

Syndicate content