Walter Morris

Coloring copoints of a planar point set

Abstract: To a set of n points in the plane, one can associate a graph that has less than n2 vertices and has the property that k-cliques in the graph correspond to vertex sets of convex k-gons in the planar point set. We prove an upper bound of 2k-1 on the size of a planar point set for which the graph has chromatic number k, matching the bound conjectured by Szekeres for the clique number.