
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
