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

Bounding the chromatic number of triangle-free graphs with fixed maximum degree ★★

Author(s): Kostochka; Reed

\begin{conjecture} A triangle-free graph with maximum degree $\Delta$ has chromatic number at most $\ceil{\frac{\Delta}{2}}+2$. % Enter your conjecture in LaTeX % You may change "conjecture" to "question" or "problem" if you prefer. \end{conjecture}

Keywords: chromatic number; girth; maximum degree; triangle free

4-regular 4-chromatic graphs of high girth ★★

Author(s): Grunbaum

\begin{problem} Do there exist 4-regular 4-chromatic graphs of arbitrarily high girth? \end{problem}

Keywords: coloring; girth

Mapping planar graphs to odd cycles ★★★

Author(s): Jaeger

\begin{conjecture} Every planar graph of girth $\ge 4k$ has a homomorphism to $C_{2k+1}$. \end{conjecture}

Keywords: girth; homomorphism; planar graph

Syndicate content