next up previous
Next: Problem 76: Equiprojective Polyhedra Up: The Open Problems Project Previous: Problem 74: Slicing Axes-Parallel


Problem 75: Edge-Coloring 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 - $ \sqrt{{n/12}}$. 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.

Bibliography

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):59-69, 2005.

BHRCW06
Prosenjit Bose, Ferran Hurtado, Eduardo Rivera-Campo, and David R. Wood.
Partitions of complete geometric graphs into plane trees.
Comput. Geom. Theory Appl., 34(2):116-125, 2006.



The Open Problems Project - December 04, 2015