list assignment


Partial List Coloring ★★★

Author(s): Iradmusa

Let $G$ be a simple graph, and for every list assignment $\mathcal{L}$ let $\lambda_{\mathcal{L}}$ be the maximum number of vertices of $G$ which are colorable with respect to $\mathcal{L}$. Define $\lambda_t = \min{ \lambda_{\mathcal{L}} }$, where the minimum is taken over all list assignments $\mathcal{L}$ with $|\mathcal{L}| = t$ for all $v \in V(G)$.

\begin{conjecture} [2] Let $G$ be a graph with list chromatic number $\chi_\ell$ and $1\leq r\leq s\leq \chi_\ell$. Then \[\frac{\lambda_r}{r}\geq\frac{\lambda_s}{s}.\] \end{conjecture}

Keywords: list assignment; list coloring

Partial List Coloring ★★★

Author(s): Albertson; Grossman; Haas

\begin{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. \end{conjecture}

Keywords: list assignment; list coloring

Syndicate content