...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Discrete Applied Mathematics >Coloring copoints of a planar point set
【24h】

Coloring copoints of a planar point set

机译：平面点集的着色共点

获取原文
获取原文并翻译 | 示例
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

To a set of n points in the plane, one can associate a graph that has less than n(2) 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 2(k-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 Erdos and Szekeres are shown to yield graphs that have very low chromatic number. The constructions are carried out in the context of pseudoline arrangements. (c) 2006 Elsevier B.V. All rights reserved.
机译：对于平面中的一组n个点，可以将一个具有少于n（2）个顶点的图关联起来，并具有以下特性：图中的k斜点对应于该点集中凸k形的顶点集。我们证明了平面点集的大小的上限为2（k-1），对于该点，图的色数为k，与Szekeres推测的集团数的边界匹配。鄂尔多斯（Erdos）和塞克（Szekeres）的构造显示出的色度数非常低。该构造是在伪线布置的情况下进行的。 （c）2006 Elsevier B.V.保留所有权利。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号