Albertson, Michael O.


Crossing numbers and coloring ★★★

Author(s): Albertson

We let $cr(G)$ denote the \Def[crossing number]{crossing number (graph theory)} of a graph $G$.

\begin{conjecture} Every graph $G$ with $\chi(G) \ge t$ satisfies $cr(G) \ge cr(K_t)$. \end{conjecture}

Keywords: coloring; complete graph; crossing number

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