Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
420744 | Discrete Applied Mathematics | 2006 | 11 Pages |
Abstract
To a set of n points in the plane, one can associate a graph that has less than n2n2 vertices and has the property that k-cliques in the graph correspond vertex sets of convex k -gons in the point set. We prove an upper bound of 2k-12k-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. Constructions of Erdős and Szekeres are shown to yield graphs that have very low chromatic number. The constructions are carried out in the context of pseudoline arrangements.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Walter Morris,