No CrossRef data available.
Article contents
Disjointness graphs of segments in the space
Published online by Cambridge University Press: 04 November 2020
Abstract
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.
MSC classification
- Type
- Paper
- Information
- Copyright
- © The Author(s), 2020. Published by Cambridge University Press
Footnotes
Supported by the National Research, Development and Innovation Office (NKFIH) project KKP-133864, ERC Advanced Grant ‘GeoScape’, the Austrian Science Fund grant Z 342-N31, and by the Ministry of Education and Science of the Russian Federation in the framework of MegaGrant no. 075-15-2019-1926.
Supported by the Cryptography ‘Lendület’ project of the Hungarian Academy of Sciences and by the National Research, Development and Innovation Office (NKFIH) projects K-116769, K-132696 and KKP-133864, by the ERC Synergy Grant ‘Dynasnet’ no. 810115 and by the Ministry of Education and Science of the Russian Federation in the framework of MegaGrant no. 075-15-2019-1926.
Supported by National Research, Development and Innovation Office, NKFIH, K-131529, KKP-133864, NKFIH-1158-6/2019 and by the Higher Educational Institutional Excellence Program 2019.