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

The Two Color Conjecture ★★

Author(s): Neumann-Lara

\begin{conjecture} If $G$ is an orientation of a simple planar graph, then there is a partition of $V(G)$ into $\{X_1,X_2\}$ so that the graph induced by $X_i$ is acyclic for $i=1,2$. \end{conjecture}

Keywords: acyclic; digraph; planar

Syndicate content