Open Problem Garden - 3-Colourability of Arrangements of Great Circles - Comments

Conjecture still open (re: 3-Colourability of Arrangements of Great Circles)

Anonymous — Thu, 22 Oct 2020 14:37:17 +0200

The conjecture is still open. I'm not sure what Cahit's arxiv preprint (http://arxiv.org/abs/math/0408363) contains, but it certainly does not contain a proof. - Manfred Scheucher

Answer to the conjecture (re: 3-Colourability of Arrangements of Great Circles)

Anonymous — Mon, 08 Sep 2014 18:23:41 +0200

This problem has been solved. See here: http://arxiv.org/abs/math/0408363 . - Anthony Hernandez

3-Colourability of Arrangements of Great Circles

David Wood — Mon, 19 Jan 2009 03:03:51 +0100

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

Subject: Graph Theory » Topological G.T. » Coloring

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.