Path in Complete Geometric Graphs

A geometric graph is a graph drawn in the plane such that a) no three vertices are colinear and b) edges are straight line segments. Edges are allowed to cross, but only transversally at interior points. A complete geometric graph is a geometric drawing of K_n.

Problem: Is there a constant c such that for any 2-coloring of the edges of a complete geometric graph on n vertices, there is a monochromatic path of length at least cn?

I do not have references for this problem.

Submitted by: Dan Archdeacon, Dept. of Math. and Stat., University of VermontBurlingtonVT 05401-1455 USA

Send comments to

December 2003