Borodin, Oleg V.

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

Acyclic list colouring of planar graphs. ★★★

Author(s): Borodin; Fon-Der-Flasss; Kostochka; Raspaud; Sopena

\begin{conjecture} Every planar graph is acyclically 5-choosable. \end{conjecture}


The Borodin-Kostochka Conjecture ★★

Author(s): Borodin; Kostochka

\begin{conjecture} Every graph with maximum degree $\Delta \geq 9$ has chromatic number at most $\max\{\Delta-1, \omega\}$. \end{conjecture}


Degenerate colorings of planar graphs ★★★

Author(s): Borodin

A graph $G$ is $k$-\emph{degenerate} if every subgraph of $G$ has a vertex of degree $\le k$.

\begin{conjecture} Every simple planar graph has a 5-coloring so that for $1 \le k \le 4$, the union of any $k$ color classes induces a $(k-1)$-degenerate graph. \end{conjecture}

Keywords: coloring; degenerate; planar

Syndicate content