# Coloring

## Grunbaum's Conjecture ★★★

Author(s): Grunbaum

**Conjecture**If is a simple loopless triangulation of an orientable surface, then the dual of is 3-edge-colorable.

## 5-local-tensions ★★

Author(s): DeVos

**Conjecture**There exists a fixed constant (probably suffices) so that every embedded (loopless) graph with edge-width has a 5-local-tension.

## Degenerate colorings of planar graphs ★★★

Author(s): Borodin

A graph is -*degenerate* if every subgraph of has a vertex of degree .

**Conjecture**Every simple planar graph has a 5-coloring so that for , the union of any color classes induces a -degenerate graph.

Keywords: coloring; degenerate; planar

## 3-Colourability of Arrangements of Great Circles ★★

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

Consider a set of great circles on a sphere with no three circles meeting at a point. The arrangement graph of 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.

**Conjecture**Every arrangement graph of a set of great circles is -colourable.

Keywords: arrangement graph; graph coloring