list coloring


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

Author(s): Allagan

\begin{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)$? \end{question}

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

List Total Colouring Conjecture ★★

Author(s): Borodin; Kostochka; Woodall

\begin{conjecture} If $G$ is the total graph of a multigraph, then $\chi_\ell(G)=\chi(G)$. \end{conjecture}

Keywords: list coloring; Total coloring; total graphs

Choosability of Graph Powers ★★

Author(s): Noel

\begin{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)?\] \end{question}

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

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

Author(s): Zhu

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

Keywords: choosability; list coloring; on-line choosability

Choice number of complete multipartite graphs with parts of size 4

Author(s):

\begin{question} What is the choice number of $K_{4*k}$ for general $k$? \end{question}

Keywords: choosability; complete multipartite graph; list coloring

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

Author(s): Noel

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

Keywords: choosability; complete multipartite graph; list coloring

Ohba's Conjecture ★★

Author(s): Ohba

\begin{conjecture} If $|V(G)|\leq 2\chi(G)+1$, then $\chi_\ell(G)=\chi(G)$. \end{conjecture}

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

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

List colorings of edge-critical graphs ★★

Author(s): Mohar

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

Keywords: edge-coloring; list coloring

Syndicate content