Sie befinden Sich nicht im Netzwerk der Universität Paderborn. Der Zugriff auf elektronische Ressourcen ist gegebenenfalls nur via VPN oder Shibboleth (DFN-AAI) möglich. mehr Informationen...
Combinatorics, probability & computing, 2021-07, Vol.30 (4), p.498-512
Ort / Verlag
Cambridge: Cambridge University Press
Erscheinungsjahr
2021
Link zum Volltext
Quelle
Alma/SFX Local Collection
Beschreibungen/Notizen
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 Ω(
n
1/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.