Coloring copoints of a planar point set |
| |
Authors: | Walter Morris |
| |
Institution: | Department of Mathematical Sciences, George Mason University, 4400 University Drive, Fairfax, VA 22030, USA |
| |
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 vertex sets of convex k-gons in the 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. 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: | Pseudoline arrangements Graph coloring Antimatroids Erdö s-Szekeres problem |
本文献已被 ScienceDirect 等数据库收录! |
|