On the Chromatic Number of the Visibility Graph of a Set of Points in the Plane
On the Chromatic Number of the Visibility Graph of a Set of Points in the Plane
复制标题
关于平面上点集可见图的色数
DOI：
--
复制
发表时间：
2005
影响因子：
0.8
通讯作者：
D. Wood
中科院分区：
文献类型：
--
作者：
Jan Kára;A. Pór;D. Wood
摘要点集 P 子集eq R2 的可见性图 V(P) 具有顶点集 P，使得只要没有其他点，两个点 v,w ∈ P 就是相邻的
在 P 中 v 和 w 之间的线段上。我们研究色数
V（P）。我们描述了 2 色和 3 色可见度图的特征。这是一个开放的
可见图的色数是否受其集团限制的问题
数量。我们的主要结果是色数的超多项式下界
（就派系数量而言）。
AbstractThe visibility graph V(P) of a point set P subseteq R2 has vertex set P, such that two points v,w ∈ P are adjacent whenever there is no other point
in P on the line segment between v and w. We study the chromatic number of
V(P). We characterise the 2- and 3-chromatic visibility graphs. It is an open
problem whether the chromatic number of a visibility graph is bounded by its clique
number. Our main result is a super-polynomial lower bound on the chromatic number
(in terms of the clique number).