list coloring

Graph Theory » Coloring » Vertex coloring

List Colourings of Complete Multipartite Graphs with 2 Big Parts ★★

Author(s): Allagan

Question Given $a,b\geq2$ , what is the smallest integer $t\geq0$ such that $\chi_\ell(K_{a,b}+K_t)= \chi(K_{a,b}+K_t)$ ?

Keywords: complete bipartite graph; complete multipartite graph; list coloring

Posted by Jon Noel
updated April 12th, 2014

add new comment

Graph Theory » Coloring

List Total Colouring Conjecture ★★

Author(s): Borodin; Kostochka; Woodall

Conjecture If $G$ is the total graph of a multigraph, then $\chi_\ell(G)=\chi(G)$ .

Keywords: list coloring; Total coloring; total graphs

Posted by Jon Noel
updated August 29th, 2013

add new comment

Graph Theory » Coloring » Vertex coloring

Choosability of Graph Powers ★★

Author(s): Noel

Question (Noel, 2013) Does there exist a function $f(k)=o(k^2)$ such that for every graph $G$ , $\text{ch}\left(G^2\right)\leq f\left(\chi\left(G^2\right)\right)?$

Keywords: choosability; chromatic number; list coloring; square of a graph

Posted by Jon Noel
updated July 13th, 2013

add new comment

Graph Theory » Coloring » Vertex coloring

Bounding the on-line choice number in terms of the choice number ★★

Author(s): Zhu

Question Are there graphs for which $\text{ch}^{\text{OL}}-\text{ch}$ is arbitrarily large?

Keywords: choosability; list coloring; on-line choosability

Posted by Jon Noel
updated April 11th, 2013

add new comment

Graph Theory » Coloring » Vertex coloring

Choice number of complete multipartite graphs with parts of size 4 ★

Author(s):

Question What is the choice number of $K_{4*k}$ for general $k$ ?

Keywords: choosability; complete multipartite graph; list coloring

Posted by Jon Noel
updated April 11th, 2013

add new comment

Graph Theory » Coloring » Vertex coloring

Choice Number of k-Chromatic Graphs of Bounded Order ★★

Author(s): Noel

Conjecture If $G$ is a $k$ -chromatic graph on at most $mk$ vertices, then $\text{ch}(G)\leq \text{ch}(K_{m*k})$ .

Keywords: choosability; complete multipartite graph; list coloring

Posted by Jon Noel
updated February 2nd, 2013

add new comment

Graph Theory » Coloring » Vertex coloring

Ohba's Conjecture ★★

Author(s): Ohba

Conjecture If $|V(G)|\leq 2\chi(G)+1$ , then $\chi_\ell(G)=\chi(G)$ .

Keywords: choosability; chromatic number; complete multipartite graph; list coloring

Posted by Jon Noel
updated May 18th, 2011

add new comment | 2 attachments

Graph Theory » Coloring » Vertex coloring

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

Keywords: list assignment; list coloring

Posted by Iradmusa
updated May 12th, 2008

add new comment

Graph Theory » Coloring » Vertex coloring

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

Posted by Iradmusa
updated May 5th, 2008

add new comment

Graph Theory » Coloring » Edge coloring

List colorings of edge-critical graphs ★★

Author(s): Mohar

Conjecture Suppose that $G$ is a $\Delta$ -edge-critical graph. Suppose that for each edge $e$ of $G$ , there is a list $L(e)$ of $\Delta$ colors. Then $G$ is $L$ -edge-colorable unless all lists are equal to each other.