Colouring $d$-degenerate graphs with large girth ★★

Author(s): Wood

\begin{question} Does there exist a $d$-degenerate graph with chromatic number $d + 1$ and girth $g$, for all $d \geq 2$ and $g \geq 3$? \end{question}

Keywords: degenerate; girth

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