NDA
Bejelentkezés
Kapcsolat
Disjointness graphs of segments |
Tartalom: | http://real.mtak.hu/73907/ |
---|---|
Archívum: | MTA Könyvtár |
Gyűjtemény: |
Status = Published
Type = Book Section |
Cím: |
Disjointness graphs of segments
|
Létrehozó: |
Pach, János
Tardos, Gábor
TĂłth, GĂ©za
|
Kiadó: |
Schloss Dagstuhl Leibniz-Zentrum fĂĽr Informatik
|
Dátum: |
2017
|
Téma: |
QA Mathematics / matematika
QA166-QA166.245 Graphs theory / gráfelmélet
|
Tartalmi leírás: |
The disjointness graph G = G (S) of a set of segments S in ℝd 3d ≥ 2, is a graph whose vertex set is S 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 χ(G) ≤ (ω(G))4 + (ω(G)) where ω(G) denotes the clique number of G. It follows, that S 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 colorings of G in which the number of colors 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. © János Pach, Gábor Tardos, and Géza Tóth.
|
Nyelv: |
angol
|
Típus: |
Book Section
NonPeerReviewed
info:eu-repo/semantics/bookPart
|
Formátum: |
text
|
Azonosító: |
Pach, János and Tardos, Gábor and Tóth, Géza (2017) Disjointness graphs of segments. In: 33rd International Symposium on Computational Geometry, SoCG 2017. Leibniz International Proceedings in Informatics, LIPIcs (77). Schloss Dagstuhl Leibniz-Zentrum für Informatik, Dagstuhl, pp. 591-5915. ISBN 9783959770385
|
Kapcsolat: |
https://doi.org/10.4230/LIPIcs.SoCG.2017.59
MTMT:3304201; doi:10.4230/LIPIcs.SoCG.2017.59
|