Coloring


Grunbaum's Conjecture ★★★

Author(s): Grunbaum

\begin{conjecture} If $G$ is a simple loopless \Def[triangulation]{triangulation (topology)} of an \Def{orientable surface}, then the dual of $G$ is 3-edge-colorable. \end{conjecture}

Keywords: coloring; surface

5-local-tensions ★★

Author(s): DeVos

\begin{conjecture} There exists a fixed constant $c$ (probably $c=4$ suffices) so that every embedded (loopless) graph with edge-width $\ge c$ has a 5-local-tension. \end{conjecture}

Keywords: coloring; surface; tension

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

3-Colourability of Arrangements of Great Circles ★★

Author(s): Felsner; Hurtado; Noy; Streinu

Consider a set $S$ of great circles on a sphere with no three circles meeting at a point. The arrangement graph of $S$ has a vertex for each intersection point, and an edge for each arc directly connecting two intersection points. So this arrangement graph is 4-regular and planar.

\begin{conjecture} Every arrangement graph of a set of great circles is $3$-colourable. \end{conjecture}

Keywords: arrangement graph; graph coloring


Syndicate content