Disjointness Graphs of Segments
Disjointness Graphs of Segments
复制标题
线段的不相交图
DOI：
--
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
G. Tóth
中科院分区：
文献类型：
--
作者：
J. Pach;G. Tardos;G. Tóth
$ {Mathbb {r}^d} $，$$ D GE 2 $$中的一组片段的dismantness图G = G（？当且仅当相应的段是不相交的情况下ω（g）表示G的集团数与空间中的线路相交或成对的脱节元素。有效的算法计算颜色的适当的颜色，其中颜色满足上述上限弧形的弧形家族的不相关图不含三角形（ω（g）= 2），但其色数任意大。
The disjointness graph G = G(?) of a set of segments ? in ${mathbb{R}^d}$, $$d ge 2$$, is a graph whose vertex set is ? and two vertices are connected by an edge if and only if the corresponding segments are disjoint. We prove that the chromatic number of G satisfies $chi (G) le {(omega (G))^4} + {(omega (G))^3}$, where ω(G) denotes the clique number of G. It follows that ? has Ω(n1/5) pairwise intersecting or pairwise disjoint elements. Stronger bounds are established for lines in space, instead of segments.We show that computing ω(G) and χ(G) for disjointness graphs of lines in space are NP-hard tasks. However, we can design efficient algorithms to compute proper colourings of G in which the number of colours satisfies the above upper bounds. One cannot expect similar results for sets of continuous arcs, instead of segments, even in the plane. We construct families of arcs whose disjointness graphs are triangle-free (ω(G) = 2), but whose chromatic numbers are arbitrarily large.