Next: Problem 76: Equiprojective Polyhedra
Up: The Open Problems Project
Previous: Problem 74: Slicing AxesParallel
Problem 75: EdgeColoring Geometric Graphs
 Statement
 For a set of n points in the plane in general position,
draw a straight segment between every pair of points.
What is the minimum number of colors that
suffice to color the edges such that no two edges that
cross have the same color?
(With the general position assumption, all crossings are
proper crossings.)
 Origin
 Ferran Hurtado: [AGH+05].
 Status/Conjectures
 Open.
 Partial and Related Results
 Each color class determines a plane subgraph of the complete graph.
Because one can arrange for n/2 pairwise crossing edges,
n/2 is a lower bound.
The best upper bound is in [BHRCW06]:
n  .
It has been conjectured that
(1  ε)n is an upper
bound for some
ε > 0.
 Appearances
 This description relies on that in the Open Problem Garden,
written by David Wood. His posting lists several related
variants.
 Categories
 geometric graphs
 Entry Revision History
 J. O'Rourke, 1 Apr. 2010.
 AGH+05

G. Araujo, Adrian Gumitrescu, Ferran Hurtado, M. Noy, and J. Urrutia.
On the chromatic number of some geometric type Kneser graphs.
Comput. Geom. Theory Appl., 32(1):5969, 2005.
 BHRCW06

Prosenjit Bose, Ferran Hurtado, Eduardo RiveraCampo, and David R. Wood.
Partitions of complete geometric graphs into plane trees.
Comput. Geom. Theory Appl., 34(2):116125, 2006.
The Open Problems Project  December 04, 2015