Open Problem Garden

Importance: High ✭✭✭

Author(s):

Subject:	Graph Theory
	» Coloring
	» » Vertex coloring

Keywords:	list assignment
	list coloring

Recomm. for undergrads: no

Posted	by:	Iradmusa
	on:	May 12th, 2008

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)$ .

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}.$

As you see this conjecture in the special case $s=\chi_\ell$ , is the conjecture of Albertson, Grossman and Haas [1]: $\lambda_t\geq\frac{tn}{\chi_\ell}$ for any $0\leq t\leq \chi_\ell$ .