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 Vermont
, Burlington, VT 05401-1455 USA
Send comments to email@example.com